fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. struct DSU
  25. {
  26. 	int S;
  27.  
  28. 	struct node
  29. 	{
  30. 		int p; ll sum;
  31. 	};
  32. 	vector<node> dsu;
  33.  
  34. 	DSU(int n)
  35. 	{
  36. 		S = n;
  37. 		for(int i = 0; i < n; i++)
  38. 		{
  39. 			node tmp;
  40. 			tmp.p = i; tmp.sum = 0;
  41. 			dsu.pb(tmp);
  42. 		}
  43. 	}
  44.  
  45. 	void reset(int n)
  46. 	{
  47. 		dsu.clear();
  48. 		S = n;
  49. 		for(int i = 0; i < n; i++)
  50. 		{
  51. 			node tmp;
  52. 			tmp.p = i; tmp.sum = 0;
  53. 			dsu.pb(tmp);
  54. 		}
  55. 	}
  56.  
  57. 	int rt(int u)
  58. 	{
  59. 		if(dsu[u].p == u) return u;
  60. 		dsu[u].p = rt(dsu[u].p);
  61. 		return dsu[u].p;
  62. 	}
  63.  
  64. 	void merge(int u, int v)
  65. 	{
  66. 		u = rt(u); v = rt(v);
  67. 		if(u == v) return ;
  68. 		if(rand()&1) swap(u, v);
  69. 		dsu[v].p = u;
  70. 		dsu[u].sum += dsu[v].sum;
  71. 	}
  72.  
  73. 	bool sameset(int u, int v)
  74. 	{
  75. 		if(rt(u) == rt(v)) return true;
  76. 		return false;
  77. 	}
  78.  
  79. 	void updsum(int u, ll s)
  80. 	{
  81. 		int r = rt(u);
  82. 		dsu[r].sum += s;
  83. 	}
  84.  
  85. 	ll getstat(int u)
  86. 	{
  87. 		return dsu[rt(u)].sum;
  88. 	}
  89. };
  90.  
  91. typedef pair<ii,ii> iiii;
  92.  
  93. const int N = 200000;
  94. DSU dsu(N+10);
  95. set<ii> edges;
  96. vector<pair<int,ii> > query;
  97. vector<iiii> question;
  98. ll cnt[N+10];
  99. int n, m, q, k;
  100.  
  101. int happiness(int u, int v)
  102. {	
  103. 	return (dsu.getstat(u)+dsu.getstat(v));	
  104. }
  105.  
  106. void clr()
  107. {
  108. 	dsu.reset(n);
  109. 	for(int i = 0; i < n; i++)
  110. 	{
  111. 		dsu.updsum(i, cnt[i]);
  112. 	}
  113. 	for(set<ii>::iterator it = edges.begin(); it != edges.end(); it++)
  114. 	{
  115. 		int u = (*it).fi; int v = (*it).se;
  116. 		dsu.merge(u,v);
  117. 	}
  118. }
  119.  
  120. ll ans[N+10];
  121.  
  122. int main()
  123. {
  124. 	ios_base::sync_with_stdio(0); cin.tie(0);
  125. 	cin>>n>>m>>q>>k;
  126. 	for(int i = 0; i < n; i++)
  127. 	{
  128. 		cin>>cnt[i];
  129. 	}
  130. 	for(int i = 0; i < m; i++)
  131. 	{
  132. 		int u, v;
  133. 		cin>>u>>v;
  134. 		u--; v--;
  135. 		edges.insert(mp(u,v));
  136. 	}
  137. 	for(int i = 0; i < q; i++)
  138. 	{
  139. 		int t, u, v;
  140. 		cin>>t>>u>>v;
  141. 		u--;
  142. 		if(t==1)
  143. 		{
  144. 			v--;
  145. 			edges.erase(mp(u,v));
  146. 			edges.erase(mp(v,u));
  147. 		}
  148. 		else
  149. 		{
  150. 			cnt[u]-=v;
  151. 			assert(cnt[u]>0);
  152. 		}
  153. 		query.pb(mp(t,mp(u,v)));
  154. 	}
  155. 	reverse(query.begin(),query.end());
  156. 	clr();
  157. 	for(int i = 0; i < k; i++)
  158. 	{
  159. 		int u, v, x;
  160. 		cin>>u>>v>>x;
  161. 		u--; v--;
  162. 		question.pb(mp(mp(u,v),mp(x,i)));
  163. 	}
  164. 	queue<pair<vector<iiii>, ii> > dq;
  165. 	dq.push(mp(question, mp(0,q+1)));
  166. 	int curval = 0;
  167. 	while(!dq.empty())
  168. 	{
  169. 		int l = dq.front().se.fi; int r = dq.front().se.se;
  170. 		if(l == r)
  171. 		{
  172. 			for(int i = 0; i < dq.front().fi.size(); i++)
  173. 			{
  174. 				if(l == q + 1) ans[dq.front().fi[i].se.se] = -1;
  175. 				else ans[dq.front().fi[i].se.se] = q-l;
  176. 			}
  177. 			dq.pop();
  178. 			continue;
  179. 		}
  180. 		int mid = (l+r)>>1;
  181. 		if(curval > mid)
  182. 		{
  183. 			curval = 0;
  184. 			clr();
  185. 		}
  186. 		bool infinity = false;
  187. 		while(curval < mid)
  188. 		{
  189. 			if(curval < q)
  190. 			{
  191. 				int t = query[curval].fi;
  192. 				int u = query[curval].se.fi;
  193. 				int v = query[curval].se.se;
  194. 				if(t == 1)
  195. 				{
  196. 					dsu.merge(u,v);
  197. 				}
  198. 				else
  199. 				{
  200. 					dsu.updsum(u, v);
  201. 				}
  202. 			}
  203. 			else
  204. 			{
  205. 				infinity = true;
  206. 			}
  207. 			curval++;
  208. 		}
  209. 		vector<iiii> L, R;
  210. 		for(int i = 0; i < dq.front().fi.size(); i++)
  211. 		{
  212. 			int u = dq.front().fi[i].fi.fi;
  213. 			int v = dq.front().fi[i].fi.se;
  214. 			ll w = dq.front().fi[i].se.fi;
  215. 			if(infinity||happiness(u,v)>=w)
  216. 			{
  217. 				L.pb(dq.front().fi[i]);
  218. 			}
  219. 			else
  220. 			{
  221. 				R.pb(dq.front().fi[i]);
  222. 			}
  223. 		}
  224. 		if(!L.empty()) dq.push(mp(L, mp(l, mid)));
  225. 		if(!R.empty()) dq.push(mp(R, mp(mid+1,r)));
  226. 		dq.pop();
  227. 	}
  228. 	for(int i = 0; i < k; i++)
  229. 	{
  230. 		cout << ans[i] << '\n';
  231. 	}
  232. }
  233.  
Success #stdin #stdout 0s 19200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dDyJTv
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!