nicuvlad76

Untitled

Nov 12th, 2022
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.13 KB | None | 0 0
  1. /* autor: Radu Stochitoiu */
  2.  
  3. #include <iostream>
  4. #include <stdio.h>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <map>
  8.  
  9. #define MAXN 2000001
  10.  
  11. using namespace std;
  12.  
  13. int TT[MAXN], RG[MAXN], n, m, q, i, j, new_father, x_tmp, y_tmp, k, K, start;
  14. int Tata_Sus[MAXN << 1], cost_intern[MAXN << 1];
  15. int dist, l, sol, pos, a, b, R, y,h=300;
  16. long long cost;
  17. vector <int> G[MAXN << 1];
  18.  
  19. int T[MAXN], L[MAXN], T2[MAXN];
  20.  
  21. struct elem {
  22. int x, y, c;
  23. } P[MAXN], P_backup[MAXN];
  24.  
  25. int cmp(elem a, elem b) {
  26. return (a.c < b.c);
  27. }
  28.  
  29. void dfs(int nod,int tata,int niv)
  30. {
  31. T2[nod]=tata;L[nod]=niv;
  32. if(niv % h == 0) tata=nod;
  33. for(int i = 0; i < G[nod].size(); ++i)
  34. {
  35. dfs(G[nod][i], tata, niv+1);
  36. T[G[nod][i]]=nod;
  37. }
  38. }
  39.  
  40. int lca(int x, int y)
  41. {
  42. while (T2[x]!=T2[y])
  43. {
  44. if(L[x] > L[y]) x=T2[x];
  45. else y=T2[y];
  46. }
  47. while(x != y)
  48. {
  49. if(L[x] > L[y]) x=T[x];
  50. else y=T[y];
  51. }
  52. return x;
  53. }
  54.  
  55.  
  56. int find(int x)
  57. {
  58. for(R = x; R != TT[R]; R = TT[R]);
  59.  
  60. // realizam compresia drumurilor
  61. while(TT[x] != x)
  62. {
  63. y = TT[x];
  64. TT[x] = R;
  65. x = y;
  66. }
  67.  
  68. return R;
  69. }
  70.  
  71. void unite(int x, int y)
  72. {
  73. // retinem noul tata pentru reprezentarea in arborele noduri-muchii
  74. // actualizam tatal si rangul
  75. if(RG[x] > RG[y]) TT[y] = x, new_father = x;
  76. else {
  77. if(RG[x] == RG[y])
  78. RG[y] ++;
  79. TT[x] = y, new_father = y;
  80. }
  81. }
  82.  
  83. int main() {
  84. freopen("trumplandia.in", "r", stdin);
  85. freopen("trumplandia.out", "w", stdout);
  86.  
  87. scanf("%d%d%d", &n, &m, &q);
  88.  
  89. for(i = 1; i <= n; ++i) {
  90. // initial fiecare nod este propriul sau tata si rangul fiecarei
  91. // multimi disjuncte este 1
  92. RG[i] = 1;
  93. TT[i] = i;
  94. Tata_Sus[i] = i;
  95. }
  96.  
  97. for(i = 1; i <= m; ++i) {
  98. // citim muchiile si le salvam pentru cand vom avea nevoie de ele
  99. // la query-uri
  100. scanf("%d%d%d", &P[i].x, &P[i].y, &P[i].c);
  101. P_backup[i] = P[i];
  102. }
  103.  
  104. // sortam muchiile
  105. sort(P + 1, P + m +1, cmp);
  106.  
  107. k = n;
  108. for(i = 1; i <= m; ++i)
  109. {
  110. // gasim cel mai inalt nod din reprezentarea multii disjuncte (Kruskal)
  111. x_tmp = find(P[i].x);
  112. y_tmp = find(P[i].y);
  113. // daca sunt in multimi diferite unim multimile
  114. if(x_tmp != y_tmp) {
  115. unite(x_tmp, y_tmp);
  116. // actualizam costul
  117. cost += P[i].c;
  118. // actualizam listele de vecini pentru arborele noduri-muchii
  119. G[++k].push_back(Tata_Sus[x_tmp]);
  120. G[k].push_back(Tata_Sus[y_tmp]);
  121. Tata_Sus[new_father] = k;
  122. // mapam muchia la costul acesteia
  123. cost_intern[k] = P[i].c;
  124. }
  125. }
  126.  
  127. printf("%lld\n", 1LL * cost);
  128. // aplicam rmq pentru query-uri in O(1)
  129. dfs(k,0, 0);
  130. while(q--) {
  131. scanf("%d", &i);
  132. // aplicam LCA si aflam costul noului arbore
  133. printf("%lld\n", 1LL*(cost + P_backup[i].c - cost_intern[lca(P_backup[i].x, P_backup[i].y)]));
  134. }
  135. return 0;
  136. }
  137.  
Advertisement
Add Comment
Please, Sign In to add comment