fork download 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <array>
  6. #include <unordered_set>
  7. #include <stack>
  8. using namespace std;
  9. #define SZ(a) (int)(a).size()
  10. typedef long long ll;
  11. typedef ll E;
  12.  
  13. E mkE(int x, int y) {
  14. 	return ((ll)x)<<32 | (ll)y;
  15. }
  16.  
  17. int fst(E e) {
  18. 	return (int)(e>>32);
  19. }
  20.  
  21. int snd(E e) {
  22. 	return (int)(e & (1ll<<32)-1);
  23. }
  24.  
  25. struct O {
  26.  
  27. 	bool tp;
  28. 	E e;
  29. 	pair<int, int> b;
  30.  
  31. 	O() {
  32. 	}
  33.  
  34. 	O(bool _tp, E _e) : tp(_tp) , e(_e) {
  35. 	}
  36.  
  37. 	O(bool _tp, pair<int, int> _b) : tp(_tp) , b(_b) {
  38. 	}
  39.  
  40. };
  41.  
  42. const auto maxn = (int)2e5;
  43. const auto maxD = (int)2e5;
  44. const auto maxsz = (int)1e9;
  45. const auto maxtg = (ll)maxn*maxsz;
  46.  
  47. struct DSU {
  48.  
  49. 	struct A {
  50. 		ll* p;
  51. 		ll s;
  52. 		A(ll* _p, ll _s) : p(_p), s(_s) {
  53. 		}
  54. 	};
  55.  
  56. 	int n;
  57. 	vector<ll> pars;
  58. 	vector<ll> szs;
  59. 	vector<O> os;
  60. 	bool rec;
  61. 	int time;
  62. 	stack<A> hist;
  63. 	stack<int> marks;
  64.  
  65. 	void assign(int _n) {
  66. 		n = _n;
  67. 		pars.assign(n, -1);
  68. 		szs.resize(n);
  69. 		rec = false;
  70. 		time = 0;
  71. 	}
  72.  
  73. 	ll store(ll* p, ll x) {
  74. 		if (rec && *p != x) {
  75. 			hist.emplace(p, *p);
  76. 		}
  77. 		return *p = x;
  78. 	}
  79.  
  80. 	ll find(ll u) {
  81. 		auto& pu = pars[u];
  82. 		return pu < 0 ? u : store(&pu, find(pu));
  83. 	}
  84.  
  85. 	void uni(ll u, ll v) {
  86. 		auto ru = find(u);
  87. 		auto rv = find(v);
  88. 		if (ru != rv) {
  89. 			if (rand() & 1) {
  90. 				swap(ru, rv);
  91. 			}
  92. 			store(&pars[rv], ru);
  93. 			store(&szs[ru],  szs[ru]+szs[rv]);
  94. 		}
  95. 	}
  96.  
  97. 	void upd(ll u, ll x) {
  98. 		auto ru = find(u);
  99. 		store(&szs[ru], szs[ru]+x);
  100. 	}
  101.  
  102. 	void move() {
  103. 		auto& o = os[time];
  104. 		if (o.tp) {
  105. 			uni(fst(o.e), snd(o.e));
  106. 		}
  107. 		else {
  108. 			upd(o.b.first, o.b.second);
  109. 		}
  110. 		time++;
  111. 		marks.push(SZ(hist));
  112. 	}
  113.  
  114. 	void jto(int time1) {
  115. 		if (time1 >= time) {
  116. 			while (time < time1) {
  117. 				move();
  118. 			}
  119. 		}
  120. 		else {
  121. 			while (SZ(marks) > time1) {
  122. 				marks.pop();
  123. 			}
  124. 			auto m = marks.empty() ? 0 : marks.top();
  125. 			while (SZ(hist) > m) {
  126. 				*hist.top().p = hist.top().s;
  127. 				hist.pop();
  128. 			}
  129. 			time = time1;
  130. 		}
  131. 	}
  132.  
  133. };
  134.  
  135. struct Q {
  136. 	int i;
  137. 	array<int, 2> us;
  138. 	ll tg;
  139. };
  140.  
  141. DSU dsu;
  142. vector<Q> qs;
  143. vector<int> ans;
  144.  
  145. bool f(Q q) {
  146. 	auto s = 0ll;
  147. 	for (auto u: q.us) {
  148. 		s += dsu.szs[dsu.find(u)];
  149. 	}
  150. 	return s < q.tg;
  151. }
  152.  
  153. int split(int l, int u, int t) {
  154. 	dsu.jto(t);
  155. 	while (l != u) {
  156. 		if (f(qs[l])) {
  157. 			swap(qs[l], qs[--u]);
  158. 		}
  159. 		else {
  160. 			l++;
  161. 		}
  162. 	}
  163. 	return l;
  164. }
  165.  
  166. void bsearch(int l, int u, int lo, int up) {
  167. 	if (l == u) {
  168. 		return;
  169. 	}
  170. 	if (lo+1 == up) {
  171. 		for (auto i = l; i < u; i++) {
  172. 			ans[qs[i].i] = lo;
  173. 		}
  174. 		return;
  175. 	}
  176. 	auto mi = (lo+up)/2;
  177. 	auto m = split(l, u, mi);
  178. 	bsearch(l, m, lo, mi);
  179. 	bsearch(m, u, mi, up);
  180. }
  181.  
  182. int main() {
  183. 	cin.sync_with_stdio(false);
  184. 	int n, m, D, S;
  185. 	cin >> n >> m >> D >> S;
  186. 	dsu.assign(n);
  187. 	for (auto u = 0; u < n; u++) {
  188. 		cin >> dsu.szs[u];
  189. 	}
  190. 	unordered_set<E> es;
  191. 	for (auto i = 0; i < m; i++) {
  192. 		int u, v;
  193. 		cin >> u >> v;
  194. 		u--; v--;
  195. 		if (u > v) {
  196. 			swap(u, v);
  197. 		}
  198. 		es.insert(mkE(u, v));
  199. 	}
  200. 	dsu.os.resize(D);
  201. 	for (auto t = D-1; t >= 0; t--) {
  202. 		int tmp;
  203. 		cin >> tmp;
  204. 		auto tp = tmp == 1;
  205. 		if (tp) {
  206. 			int u, v;
  207. 			cin >> u >> v;
  208. 			u--; v--;
  209. 			if (u > v) {
  210. 				swap(u, v);
  211. 			}
  212. 			auto e = mkE(u, v);
  213. 			es.erase(e);
  214. 			dsu.os[t] = O(tp, e);
  215. 		}
  216. 		else {
  217. 			int u, x;
  218. 			cin >> u >> x;
  219. 			u--;
  220. 			dsu.szs[u] -= x;
  221. 			dsu.os[t] = O(tp, make_pair(u, x));
  222. 		}
  223. 	}
  224. 	for (auto e: es) {
  225. 		dsu.uni(fst(e), snd(e));
  226. 	}
  227. 	dsu.rec = true;
  228. 	qs.resize(S);
  229. 	for (auto i = 0; i < S; i++) {
  230. 		int u, v;
  231. 		cin >> u >> v;
  232. 		u--; v--;
  233. 		ll tg;
  234. 		cin >> tg;
  235. 		qs[i] = {i, {u, v}, tg};
  236. 	}
  237. 	ans.resize(S);
  238. 	bsearch(0, S, -1, D+1);
  239. 	for (auto i = 0; i < S; i++) {
  240. 		printf("%d\n", D-1-ans[i]);
  241. 	}
  242. 	return 0;
  243. }
  244.  
Runtime error #stdin #stdout #stderr 0s 16080KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/G7xAEC
language:
C++14 (gcc 8.3)
created:
8 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!