fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const int INF = 1e9 + 20;
  6.  
  7. int n;
  8. int m[2];
  9. int qnum;
  10.  
  11. struct node {
  12. 	node* c[2];
  13. 	node* p;
  14. 	bool flip;
  15.  
  16. 	int idx;
  17. 	int val;
  18. 	node* max_node;
  19.  
  20. 	int d() {
  21. 		assert(p);
  22. 		return p->c[1] == this;
  23. 	}
  24.  
  25. 	bool r() {
  26. 		return !(p && p->c[d()] == this);
  27. 	}
  28.  
  29. 	void do_flip() {
  30. 		flip = !flip;
  31. 	}
  32.  
  33. 	void propagate() {
  34. 		if (flip) {
  35. 			flip = false;
  36. 			swap(c[0], c[1]);
  37. 			for (int i = 0; i < 2; i++) {
  38. 				if (c[i]) c[i]->do_flip();
  39. 			}
  40. 		}
  41. 	}
  42.  
  43. 	void upd() {
  44. 		max_node = this;
  45. 		for (int i = 0; i < 2; i++) {
  46. 			if (c[i] && c[i]->max_node->val > max_node->val) {
  47. 				max_node = c[i]->max_node;
  48. 			}
  49. 		}
  50. 	}
  51.  
  52. 	void propagate_all() {
  53. 		if (!r()) p->propagate_all();
  54. 		propagate();
  55. 	}
  56.  
  57. 	void rot() {
  58. 		int x = d();
  59. 		node* pa = p;
  60. 		node* ch = c[!x];
  61.  
  62. 		if (!pa->r()) pa->p->c[pa->d()] = this;
  63. 		p = pa->p;
  64.  
  65. 		pa->c[x] = ch;
  66. 		if (ch) ch->p = pa;
  67.  
  68. 		c[!x] = pa;
  69. 		pa->p = this;
  70.  
  71. 		pa->upd();
  72. 		upd();
  73. 	}
  74.  
  75. 	void splay() {
  76. 		propagate_all();
  77. 		while (!r()) {
  78. 			if (!p->r()) {
  79. 				if (p->d() == d()) p->rot();
  80. 				else rot();
  81. 			}
  82. 			rot();
  83. 		}
  84. 	}
  85.  
  86. 	void expose() {
  87. 		splay();
  88. 		while (p) {
  89. 			p->splay();
  90. 			p->c[1] = this;
  91. 			rot();
  92. 		}
  93. 		c[1] = NULL;
  94. 		upd();
  95. 		assert(r());
  96. 	}
  97.  
  98. 	void make_root() {
  99. 		expose();
  100. 		assert(r());
  101. 		do_flip();
  102. 	}
  103.  
  104. 	void cut() {
  105. 		expose();
  106. 		assert(c[1] == NULL);
  107. 		assert(!flip);
  108. 		assert(c[0]);
  109. 		c[0]->p = NULL;
  110. 		c[0] = NULL;
  111. 		upd();
  112. 	}
  113.  
  114. 	void link(node* v) {
  115. 		assert(get_root() != v->get_root());
  116. 		make_root();
  117. 		p = v;
  118. 	}
  119.  
  120. 	node* get_root() {
  121. 		expose();
  122. 		node* v = this;
  123. 		while (true) {
  124. 			v->propagate();
  125. 			if (!v->c[0]) break;
  126. 			v = v->c[0];
  127. 		}
  128. 		v->expose();
  129. 		return v;
  130. 	}
  131.  
  132. 	friend node* get_max(node* a, node* b) {
  133. 		assert(a && b);
  134. 		a->make_root();
  135. 		b->expose();
  136. 		assert(b->max_node);
  137. 		return b->max_node;
  138. 	}
  139. };
  140.  
  141. struct edge {
  142. 	int a, b;
  143. 	int k;
  144.  
  145. 	friend istream& operator >> (istream& i, edge& e) {
  146. 		cin >> e.a >> e.b >> e.k;
  147. 		e.a--; e.b--;
  148. 		return i;
  149. 	}
  150.  
  151. 	bool operator < (const edge& o) const {
  152. 		return k < o.k;
  153. 	}
  154. };
  155. vector<edge> trees[2];
  156. vector<edge> tree_mst[2];
  157.  
  158. vector<int> uf;
  159. void reset_uf() {
  160. 	fill(uf.begin(), uf.end(), -1);
  161. }
  162. int getpar(int a) {
  163. 	return uf[a] < 0 ? a : (uf[a] = getpar(uf[a]));
  164. }
  165. bool unite(int a, int b) {
  166. 	a = getpar(a);
  167. 	b = getpar(b);
  168. 	if (a == b) return false;
  169. 	if (-uf[a] < -uf[b]) swap(a, b);
  170. 	uf[a] += uf[b];
  171. 	uf[b] = a;
  172. 	return true;
  173. }
  174.  
  175. void solve_mst(vector<edge>& edges, vector<edge>& mst) {
  176. 	sort(edges.begin(), edges.end());
  177. 	reset_uf();
  178. 	for (int e = 0; e < int(edges.size()); e++) {
  179. 		if (unite(edges[e].a, edges[e].b)) {
  180. 			mst.push_back(edges[e]);
  181. 		}
  182. 	}
  183. 	assert(int(mst.size()) == n-1);
  184. }
  185.  
  186. vector<node> vert_nodes;
  187. vector<node> edge_nodes;
  188.  
  189. int main() {
  190. 	ios::sync_with_stdio(0), cin.tie(0);
  191. 	cin >> n >> m[0] >> m[1] >> qnum;
  192. 	uf.resize(n);
  193. 	for (int z = 0; z < 2; z++) {
  194. 		trees[z].resize(m[z]);
  195. 		for (int e = 0; e < m[z]; e++) {
  196. 			cin >> trees[z][e];
  197. 		}
  198. 		solve_mst(trees[z], tree_mst[z]);
  199. 	}
  200.  
  201. 	vert_nodes.resize(n);
  202. 	for (int i = 0; i < n; i++) {
  203. 		vert_nodes[i].val = -INF;
  204. 		vert_nodes[i].idx = -1;
  205. 		vert_nodes[i].upd();
  206. 	}
  207. 	edge_nodes.resize(n-1);
  208. 	for (int e = 0; e < n-1; e++) {
  209. 		edge_nodes[e].val = tree_mst[0][e].k;
  210. 		edge_nodes[e].idx = e;
  211. 		edge_nodes[e].upd();
  212. 	}
  213. 	ll cur = 0;
  214. 	for (int e = 0; e < n-1; e++) {
  215. 		int a = tree_mst[0][e].a;
  216. 		int b = tree_mst[0][e].b;
  217. 		cur += tree_mst[0][e].k;
  218. 		vert_nodes[a].link(&edge_nodes[e]);
  219. 		vert_nodes[b].link(&edge_nodes[e]);
  220. 	}
  221.  
  222. 	vector<int> ntr;
  223. 	ntr.reserve(n-1);
  224. 	for (int e = 0; e < n-1; e++) {
  225. 		int a = tree_mst[1][e].a;
  226. 		int b = tree_mst[1][e].b;
  227. 		node* max_path = get_max(&vert_nodes[a], &vert_nodes[b]);
  228. 		if (max_path->val == -INF) continue;
  229. 		int idx = max_path->idx;
  230. 		max_path->make_root();
  231. 		vert_nodes[tree_mst[0][idx].a].cut();
  232. 		vert_nodes[tree_mst[0][idx].b].cut();
  233. 		vert_nodes[a].link(&vert_nodes[b]);
  234. 		ntr.push_back(tree_mst[1][e].k - max_path->val);
  235. 	}
  236. 	sort(ntr.begin(), ntr.end());
  237. 	vector<pair<int, int> > queries(qnum);
  238. 	for (int i = 0; i < qnum; i++) {
  239. 		int t;
  240. 		cin >> t;
  241. 		queries[i] = make_pair(t, i);
  242. 	}
  243. 	sort(queries.begin(), queries.end());
  244. 	vector<ll> answers(qnum);
  245. 	for (int i = 0, j = 0; i < qnum; i++) {
  246. 		int t = queries[i].first;
  247. 		int idx = queries[i].second;
  248. 		while (j < int(ntr.size()) && ntr[j] <= 2*t) {
  249. 			cur += ntr[j];
  250. 			j++;
  251. 		}
  252. 		answers[idx] = cur + ll(t) * (-j + (n-1-j));
  253. 	}
  254. 	for (int i = 0; i < qnum; i++) {
  255. 		cout << answers[i] << '\n';
  256. 	}
  257. }
  258.  
Success #stdin #stdout 0s 4256KB
comments (?)
stdin
copy 
5 4 4 4
1 3 2
1 2 0
3 5 5
3 4 10
5 4 7
2 3 6
1 2 1000
3 4 1000
0
1
2
3
stdout
copy 
14
16
18
18
https://ideone.com/o0uvmX
language:
C++14 (gcc 8.3)
created:
5 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!