#include <algorithm>
#include <cassert>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int BLOCK_SIZE = 1000;
struct edge {
int u, v, w;
static bool compDecrW(edge &e1, edge &e2) { return e1.w > e2.w; }
};
struct update {
int e, w;
};
struct query {
int id;
int v, w;
static bool compDecrW(query &q1, query &q2) { return q1.w > q2.w; }
};
struct rollback_dsu {
struct change {
int oldRoot, newRoot;
};
vector<int> parent;
vector<int> compSize;
stack<change> changes;
rollback_dsu(int cntNodes) {
parent.resize(cntNodes);
compSize.resize(cntNodes, 1);
for (int i = 0; i < cntNodes; i++) {
parent[i] = i;
}
}
int findRoot(int x) {
while (parent[x] != x)
x = parent[x];
return x;
}
void unite(int x, int y) {
int rootX = findRoot(x);
int rootY = findRoot(y);
if (rootX == rootY)
return;
if (compSize[rootX] <= compSize[rootY]) {
parent[rootX] = rootY;
compSize[rootY] += compSize[rootX];
changes.push(change{rootX, rootY});
} else {
parent[rootY] = rootX;
compSize[rootX] += compSize[rootY];
changes.push(change{rootY, rootX});
}
}
void markAsStable() {
while (!changes.empty())
changes.pop();
}
void rollbackToStable() {
while (!changes.empty()) {
auto [oldRoot, newRoot] = changes.top();
changes.pop();
parent[oldRoot] = oldRoot;
compSize[newRoot] -= compSize[oldRoot];
}
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<edge> edges(m);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
u--;
v--;
edges[i] = edge{u, v, w};
}
int q;
cin >> q;
vector<bool> changed(m, false);
for (int i = 0; i < q; i += BLOCK_SIZE) {
vector<int> t(min(BLOCK_SIZE, q - i));
vector<update> updates;
vector<query> queries;
fill(changed.begin(), changed.end(), false);
for (int j = 0; j < min(BLOCK_SIZE, q - i); j++) {
cin >> t[j];
if (t[j] == 1) {
int e, w;
cin >> e >> w;
e--;
updates.push_back(update{e, w});
changed[e] = true;
} else {
int v, w;
cin >> v >> w;
v--;
queries.push_back(query{(int)queries.size(), v, w});
}
}
vector<vector<edge>> additionalEdges(queries.size());
int queryInd = 0, updateInd = 0;
for (int j = 0; j < min(BLOCK_SIZE, q - i); j++) {
if (t[j] == 1) {
edges[updates[updateInd].e].w = updates[updateInd].w;
updateInd++;
} else {
assert(queryInd < queries.size());
for (auto u : updates) {
if (edges[u.e].w >= queries[queryInd].w)
additionalEdges[queryInd].push_back(edges[u.e]);
}
queryInd++;
}
}
vector<edge> unchanged;
for (int j = 0; j < m; j++) {
if (!changed[j])
unchanged.push_back(edges[j]);
}
sort(unchanged.begin(), unchanged.end(), edge::compDecrW);
sort(queries.begin(), queries.end(), query::compDecrW);
auto dsu = rollback_dsu(n);
int edgePtr = 0;
vector<int> ans(queries.size());
for (int j = 0; j < queries.size(); j++) {
while (edgePtr < unchanged.size() &&
unchanged[edgePtr].w >= queries[j].w) {
dsu.unite(unchanged[edgePtr].u, unchanged[edgePtr].v);
edgePtr++;
}
dsu.markAsStable();
for (auto e : additionalEdges[queries[j].id]) {
dsu.unite(e.u, e.v);
}
assert(queries[j].id >= 0 && queries[j].id < ans.size());
ans[queries[j].id] = dsu.compSize[dsu.findRoot(queries[j].v)];
dsu.rollbackToStable();
}
for (auto x : ans) {
cout << x << endl;
}
}
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from bridges.cpp:2:
bridges.cpp: In function 'int main()':
bridges.cpp:143:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | assert(queryInd < queries.size());
| ~~~~~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:165:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | for (int j = 0; j < queries.size(); j++) {
| ~~^~~~~~~~~~~~~~~~
bridges.cpp:166:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | while (edgePtr < unchanged.size() &&
| ~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from bridges.cpp:2:
bridges.cpp:178:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | assert(queries[j].id >= 0 && queries[j].id < ans.size());
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
31 ms |
2556 KB |
Output is correct |
4 |
Correct |
13 ms |
344 KB |
Output is correct |
5 |
Correct |
31 ms |
3176 KB |
Output is correct |
6 |
Correct |
28 ms |
3416 KB |
Output is correct |
7 |
Correct |
32 ms |
4004 KB |
Output is correct |
8 |
Correct |
33 ms |
2372 KB |
Output is correct |
9 |
Correct |
37 ms |
5200 KB |
Output is correct |
10 |
Correct |
33 ms |
2648 KB |
Output is correct |
11 |
Correct |
35 ms |
2460 KB |
Output is correct |
12 |
Correct |
43 ms |
3264 KB |
Output is correct |
13 |
Correct |
37 ms |
2908 KB |
Output is correct |
14 |
Correct |
37 ms |
2476 KB |
Output is correct |
15 |
Correct |
42 ms |
2716 KB |
Output is correct |
16 |
Correct |
35 ms |
4160 KB |
Output is correct |
17 |
Correct |
40 ms |
3680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
996 ms |
4952 KB |
Output is correct |
2 |
Correct |
984 ms |
4828 KB |
Output is correct |
3 |
Correct |
988 ms |
4912 KB |
Output is correct |
4 |
Correct |
991 ms |
4892 KB |
Output is correct |
5 |
Correct |
977 ms |
4836 KB |
Output is correct |
6 |
Correct |
1174 ms |
8864 KB |
Output is correct |
7 |
Correct |
1086 ms |
8744 KB |
Output is correct |
8 |
Correct |
1105 ms |
8724 KB |
Output is correct |
9 |
Correct |
132 ms |
864 KB |
Output is correct |
10 |
Correct |
633 ms |
7024 KB |
Output is correct |
11 |
Correct |
619 ms |
6124 KB |
Output is correct |
12 |
Correct |
869 ms |
5176 KB |
Output is correct |
13 |
Correct |
766 ms |
3988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
754 ms |
3952 KB |
Output is correct |
2 |
Correct |
489 ms |
4904 KB |
Output is correct |
3 |
Correct |
804 ms |
5952 KB |
Output is correct |
4 |
Correct |
743 ms |
4168 KB |
Output is correct |
5 |
Correct |
128 ms |
520 KB |
Output is correct |
6 |
Correct |
763 ms |
4952 KB |
Output is correct |
7 |
Correct |
699 ms |
3848 KB |
Output is correct |
8 |
Correct |
653 ms |
3208 KB |
Output is correct |
9 |
Correct |
584 ms |
3516 KB |
Output is correct |
10 |
Correct |
583 ms |
3072 KB |
Output is correct |
11 |
Correct |
528 ms |
3288 KB |
Output is correct |
12 |
Correct |
487 ms |
2480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1374 ms |
5284 KB |
Output is correct |
2 |
Correct |
131 ms |
1796 KB |
Output is correct |
3 |
Correct |
147 ms |
6272 KB |
Output is correct |
4 |
Correct |
81 ms |
6220 KB |
Output is correct |
5 |
Correct |
758 ms |
7096 KB |
Output is correct |
6 |
Correct |
1305 ms |
8760 KB |
Output is correct |
7 |
Correct |
758 ms |
7184 KB |
Output is correct |
8 |
Correct |
733 ms |
5580 KB |
Output is correct |
9 |
Correct |
715 ms |
5452 KB |
Output is correct |
10 |
Correct |
695 ms |
5744 KB |
Output is correct |
11 |
Correct |
1096 ms |
7268 KB |
Output is correct |
12 |
Correct |
1055 ms |
7552 KB |
Output is correct |
13 |
Correct |
1041 ms |
7772 KB |
Output is correct |
14 |
Correct |
722 ms |
7292 KB |
Output is correct |
15 |
Correct |
760 ms |
7248 KB |
Output is correct |
16 |
Correct |
1408 ms |
8500 KB |
Output is correct |
17 |
Correct |
1375 ms |
8600 KB |
Output is correct |
18 |
Correct |
1394 ms |
8676 KB |
Output is correct |
19 |
Correct |
1366 ms |
8724 KB |
Output is correct |
20 |
Correct |
1171 ms |
8268 KB |
Output is correct |
21 |
Correct |
1167 ms |
8516 KB |
Output is correct |
22 |
Correct |
1308 ms |
8764 KB |
Output is correct |
23 |
Correct |
808 ms |
6768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
996 ms |
4952 KB |
Output is correct |
2 |
Correct |
984 ms |
4828 KB |
Output is correct |
3 |
Correct |
988 ms |
4912 KB |
Output is correct |
4 |
Correct |
991 ms |
4892 KB |
Output is correct |
5 |
Correct |
977 ms |
4836 KB |
Output is correct |
6 |
Correct |
1174 ms |
8864 KB |
Output is correct |
7 |
Correct |
1086 ms |
8744 KB |
Output is correct |
8 |
Correct |
1105 ms |
8724 KB |
Output is correct |
9 |
Correct |
132 ms |
864 KB |
Output is correct |
10 |
Correct |
633 ms |
7024 KB |
Output is correct |
11 |
Correct |
619 ms |
6124 KB |
Output is correct |
12 |
Correct |
869 ms |
5176 KB |
Output is correct |
13 |
Correct |
766 ms |
3988 KB |
Output is correct |
14 |
Correct |
754 ms |
3952 KB |
Output is correct |
15 |
Correct |
489 ms |
4904 KB |
Output is correct |
16 |
Correct |
804 ms |
5952 KB |
Output is correct |
17 |
Correct |
743 ms |
4168 KB |
Output is correct |
18 |
Correct |
128 ms |
520 KB |
Output is correct |
19 |
Correct |
763 ms |
4952 KB |
Output is correct |
20 |
Correct |
699 ms |
3848 KB |
Output is correct |
21 |
Correct |
653 ms |
3208 KB |
Output is correct |
22 |
Correct |
584 ms |
3516 KB |
Output is correct |
23 |
Correct |
583 ms |
3072 KB |
Output is correct |
24 |
Correct |
528 ms |
3288 KB |
Output is correct |
25 |
Correct |
487 ms |
2480 KB |
Output is correct |
26 |
Correct |
999 ms |
4720 KB |
Output is correct |
27 |
Correct |
1042 ms |
6508 KB |
Output is correct |
28 |
Correct |
1012 ms |
4832 KB |
Output is correct |
29 |
Correct |
762 ms |
3416 KB |
Output is correct |
30 |
Correct |
1029 ms |
5812 KB |
Output is correct |
31 |
Correct |
1049 ms |
5948 KB |
Output is correct |
32 |
Correct |
1044 ms |
5756 KB |
Output is correct |
33 |
Correct |
967 ms |
4872 KB |
Output is correct |
34 |
Correct |
973 ms |
4616 KB |
Output is correct |
35 |
Correct |
995 ms |
4660 KB |
Output is correct |
36 |
Correct |
799 ms |
3720 KB |
Output is correct |
37 |
Correct |
791 ms |
3956 KB |
Output is correct |
38 |
Correct |
799 ms |
3684 KB |
Output is correct |
39 |
Correct |
740 ms |
3268 KB |
Output is correct |
40 |
Correct |
744 ms |
3044 KB |
Output is correct |
41 |
Correct |
735 ms |
3576 KB |
Output is correct |
42 |
Correct |
663 ms |
3212 KB |
Output is correct |
43 |
Correct |
657 ms |
2952 KB |
Output is correct |
44 |
Correct |
626 ms |
3244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
31 ms |
2556 KB |
Output is correct |
4 |
Correct |
13 ms |
344 KB |
Output is correct |
5 |
Correct |
31 ms |
3176 KB |
Output is correct |
6 |
Correct |
28 ms |
3416 KB |
Output is correct |
7 |
Correct |
32 ms |
4004 KB |
Output is correct |
8 |
Correct |
33 ms |
2372 KB |
Output is correct |
9 |
Correct |
37 ms |
5200 KB |
Output is correct |
10 |
Correct |
33 ms |
2648 KB |
Output is correct |
11 |
Correct |
35 ms |
2460 KB |
Output is correct |
12 |
Correct |
43 ms |
3264 KB |
Output is correct |
13 |
Correct |
37 ms |
2908 KB |
Output is correct |
14 |
Correct |
37 ms |
2476 KB |
Output is correct |
15 |
Correct |
42 ms |
2716 KB |
Output is correct |
16 |
Correct |
35 ms |
4160 KB |
Output is correct |
17 |
Correct |
40 ms |
3680 KB |
Output is correct |
18 |
Correct |
996 ms |
4952 KB |
Output is correct |
19 |
Correct |
984 ms |
4828 KB |
Output is correct |
20 |
Correct |
988 ms |
4912 KB |
Output is correct |
21 |
Correct |
991 ms |
4892 KB |
Output is correct |
22 |
Correct |
977 ms |
4836 KB |
Output is correct |
23 |
Correct |
1174 ms |
8864 KB |
Output is correct |
24 |
Correct |
1086 ms |
8744 KB |
Output is correct |
25 |
Correct |
1105 ms |
8724 KB |
Output is correct |
26 |
Correct |
132 ms |
864 KB |
Output is correct |
27 |
Correct |
633 ms |
7024 KB |
Output is correct |
28 |
Correct |
619 ms |
6124 KB |
Output is correct |
29 |
Correct |
869 ms |
5176 KB |
Output is correct |
30 |
Correct |
766 ms |
3988 KB |
Output is correct |
31 |
Correct |
754 ms |
3952 KB |
Output is correct |
32 |
Correct |
489 ms |
4904 KB |
Output is correct |
33 |
Correct |
804 ms |
5952 KB |
Output is correct |
34 |
Correct |
743 ms |
4168 KB |
Output is correct |
35 |
Correct |
128 ms |
520 KB |
Output is correct |
36 |
Correct |
763 ms |
4952 KB |
Output is correct |
37 |
Correct |
699 ms |
3848 KB |
Output is correct |
38 |
Correct |
653 ms |
3208 KB |
Output is correct |
39 |
Correct |
584 ms |
3516 KB |
Output is correct |
40 |
Correct |
583 ms |
3072 KB |
Output is correct |
41 |
Correct |
528 ms |
3288 KB |
Output is correct |
42 |
Correct |
487 ms |
2480 KB |
Output is correct |
43 |
Correct |
1374 ms |
5284 KB |
Output is correct |
44 |
Correct |
131 ms |
1796 KB |
Output is correct |
45 |
Correct |
147 ms |
6272 KB |
Output is correct |
46 |
Correct |
81 ms |
6220 KB |
Output is correct |
47 |
Correct |
758 ms |
7096 KB |
Output is correct |
48 |
Correct |
1305 ms |
8760 KB |
Output is correct |
49 |
Correct |
758 ms |
7184 KB |
Output is correct |
50 |
Correct |
733 ms |
5580 KB |
Output is correct |
51 |
Correct |
715 ms |
5452 KB |
Output is correct |
52 |
Correct |
695 ms |
5744 KB |
Output is correct |
53 |
Correct |
1096 ms |
7268 KB |
Output is correct |
54 |
Correct |
1055 ms |
7552 KB |
Output is correct |
55 |
Correct |
1041 ms |
7772 KB |
Output is correct |
56 |
Correct |
722 ms |
7292 KB |
Output is correct |
57 |
Correct |
760 ms |
7248 KB |
Output is correct |
58 |
Correct |
1408 ms |
8500 KB |
Output is correct |
59 |
Correct |
1375 ms |
8600 KB |
Output is correct |
60 |
Correct |
1394 ms |
8676 KB |
Output is correct |
61 |
Correct |
1366 ms |
8724 KB |
Output is correct |
62 |
Correct |
1171 ms |
8268 KB |
Output is correct |
63 |
Correct |
1167 ms |
8516 KB |
Output is correct |
64 |
Correct |
1308 ms |
8764 KB |
Output is correct |
65 |
Correct |
808 ms |
6768 KB |
Output is correct |
66 |
Correct |
999 ms |
4720 KB |
Output is correct |
67 |
Correct |
1042 ms |
6508 KB |
Output is correct |
68 |
Correct |
1012 ms |
4832 KB |
Output is correct |
69 |
Correct |
762 ms |
3416 KB |
Output is correct |
70 |
Correct |
1029 ms |
5812 KB |
Output is correct |
71 |
Correct |
1049 ms |
5948 KB |
Output is correct |
72 |
Correct |
1044 ms |
5756 KB |
Output is correct |
73 |
Correct |
967 ms |
4872 KB |
Output is correct |
74 |
Correct |
973 ms |
4616 KB |
Output is correct |
75 |
Correct |
995 ms |
4660 KB |
Output is correct |
76 |
Correct |
799 ms |
3720 KB |
Output is correct |
77 |
Correct |
791 ms |
3956 KB |
Output is correct |
78 |
Correct |
799 ms |
3684 KB |
Output is correct |
79 |
Correct |
740 ms |
3268 KB |
Output is correct |
80 |
Correct |
744 ms |
3044 KB |
Output is correct |
81 |
Correct |
735 ms |
3576 KB |
Output is correct |
82 |
Correct |
663 ms |
3212 KB |
Output is correct |
83 |
Correct |
657 ms |
2952 KB |
Output is correct |
84 |
Correct |
626 ms |
3244 KB |
Output is correct |
85 |
Correct |
1593 ms |
10668 KB |
Output is correct |
86 |
Correct |
162 ms |
8240 KB |
Output is correct |
87 |
Correct |
103 ms |
11416 KB |
Output is correct |
88 |
Correct |
958 ms |
10012 KB |
Output is correct |
89 |
Correct |
1657 ms |
10780 KB |
Output is correct |
90 |
Correct |
988 ms |
10104 KB |
Output is correct |
91 |
Correct |
1016 ms |
7612 KB |
Output is correct |
92 |
Correct |
1010 ms |
7392 KB |
Output is correct |
93 |
Correct |
1132 ms |
9776 KB |
Output is correct |
94 |
Correct |
1331 ms |
9660 KB |
Output is correct |
95 |
Correct |
1334 ms |
9352 KB |
Output is correct |
96 |
Correct |
1331 ms |
11368 KB |
Output is correct |
97 |
Correct |
860 ms |
8776 KB |
Output is correct |
98 |
Correct |
777 ms |
7996 KB |
Output is correct |
99 |
Correct |
1611 ms |
10452 KB |
Output is correct |
100 |
Correct |
1612 ms |
10556 KB |
Output is correct |
101 |
Correct |
1657 ms |
10528 KB |
Output is correct |
102 |
Correct |
1682 ms |
10372 KB |
Output is correct |
103 |
Correct |
1475 ms |
12964 KB |
Output is correct |
104 |
Correct |
1463 ms |
13180 KB |
Output is correct |
105 |
Correct |
1157 ms |
9856 KB |
Output is correct |
106 |
Correct |
1014 ms |
8792 KB |
Output is correct |
107 |
Correct |
1235 ms |
9564 KB |
Output is correct |
108 |
Correct |
1470 ms |
11812 KB |
Output is correct |
109 |
Correct |
981 ms |
10416 KB |
Output is correct |