#include <bits/stdc++.h>
using namespace std;
const int BLOCK = 900;
struct RollbackDSU {
vector<int> root; // parent
vector<int> sz; // size
vector<pair<int, int>> operations; // (modified_id, size[id]). If size[id] == -1, then the parent changes
void init(int n) {
sz.assign(n, 1);
root.assign(n, 0);
iota(begin(root), end(root), 0);
}
int find(int n) {
while (root[n] != n) {
n = root[n];
}
return n;
}
bool join(int a, int b, bool revert = false) {
a = find(a);
b = find(b);
if (a == b) {
return false;
}
if (sz[a] < sz[b]) {
swap(a, b);
}
if (revert) {
operations.emplace_back(b, -1); // b's parent changes
operations.emplace_back(a, sz[a]); // a's previous size
}
sz[a] += sz[b];
root[b] = a;
return true;
}
void rollback() {
reverse(begin(operations), end(operations));
for (auto& op : operations) {
if (op.second == -1) {
root[op.first] = op.first;
} else {
sz[op.first] = op.second;
}
}
operations.clear();
}
int getSize(int n) {
return sz[find(n)];
}
};
struct Edge {
int u, v, weight;
Edge(int u, int v, int w) : u(u), v(v), weight(w) {}
bool operator<(const Edge& o) const {
return weight > o.weight;
}
};
struct Query {
int start, weight, time;
Query(int s, int w, int t) : start(s), weight(w), time(t) {}
bool operator<(const Query& o) const {
return weight > o.weight;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
vector<Edge> edge;
vector<pair<int, int>> update(m, make_pair(-1, -1)); // (weight, update_time)
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
edge.emplace_back(u, v, w);
}
int q;
cin >> q;
RollbackDSU DSU;
vector<pair<int, int>> ans; // (time, answer)
for (int qi = 0; qi < q; qi += BLOCK) {
vector<Query> query; // query: (time, start, weight)
vector<tuple<int, int, int, int>> changed; // (id, weight, time1, time2) -> the id-th edge has weight for time peirod [time1, time2]
vector<Edge> unchanged; // ids of unchanged edges
DSU.init(n);
for (int i = qi; i < qi + BLOCK && i < q; i++) {
int t, a, b;
cin >> t >> a >> b;
a--;
if (t == 1) {
if (update[a] == make_pair(-1, -1)) {
update[a].first = edge[a].weight;
}
changed.emplace_back(a, update[a].first, update[a].second, i - 1); // the current weight lasts between (t1, t2)
update[a] = {b, i};
} else if (t == 2) {
query.emplace_back(a, b, i);
}
}
for (int i = 0; i < m; i++) {
if (update[i] != make_pair(-1, -1)) {
changed.emplace_back(i, update[i].first, update[i].second, qi + BLOCK);
// Update original edge's weight with latest update
edge[i].weight = update[i].first;
update[i] = make_pair(-1, -1);
} else {
unchanged.emplace_back(edge[i]);
}
}
sort(begin(unchanged), end(unchanged));
sort(begin(query), end(query));
for (int i = 0, j = 0; i < query.size(); i++) { // O(BLOCK) iterations
while (j < unchanged.size() && unchanged[j].weight >= query[i].weight) {
DSU.join(unchanged[j].u, unchanged[j].v);
j++;
}
for (auto& c : changed) { // O(BLOCK log n)
int id, w, t1, t2;
tie(id, w, t1, t2) = c;
if (t1 <= query[i].time && query[i].time <= t2 && w >= query[i].weight) {
DSU.join(edge[id].u, edge[id].v, true);
}
}
ans.emplace_back(query[i].time, DSU.getSize(query[i].start));
DSU.rollback();
}
}
sort(begin(ans), end(ans));
for (auto& i : ans) {
cout << i.second << "\n";
}
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:136:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0, j = 0; i < query.size(); i++) { // O(BLOCK) iterations
~~^~~~~~~~~~~~~~
bridges.cpp:137:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < unchanged.size() && unchanged[j].weight >= query[i].weight) {
~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
252 KB |
Output is correct |
3 |
Correct |
40 ms |
504 KB |
Output is correct |
4 |
Correct |
7 ms |
632 KB |
Output is correct |
5 |
Correct |
17 ms |
504 KB |
Output is correct |
6 |
Correct |
18 ms |
504 KB |
Output is correct |
7 |
Correct |
20 ms |
504 KB |
Output is correct |
8 |
Correct |
21 ms |
504 KB |
Output is correct |
9 |
Correct |
22 ms |
504 KB |
Output is correct |
10 |
Correct |
22 ms |
504 KB |
Output is correct |
11 |
Correct |
22 ms |
504 KB |
Output is correct |
12 |
Correct |
24 ms |
504 KB |
Output is correct |
13 |
Correct |
29 ms |
504 KB |
Output is correct |
14 |
Correct |
27 ms |
504 KB |
Output is correct |
15 |
Correct |
24 ms |
636 KB |
Output is correct |
16 |
Correct |
21 ms |
504 KB |
Output is correct |
17 |
Correct |
21 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1480 ms |
3876 KB |
Output is correct |
2 |
Correct |
1509 ms |
3888 KB |
Output is correct |
3 |
Correct |
1507 ms |
3992 KB |
Output is correct |
4 |
Correct |
1605 ms |
3972 KB |
Output is correct |
5 |
Correct |
1599 ms |
3976 KB |
Output is correct |
6 |
Correct |
2418 ms |
4200 KB |
Output is correct |
7 |
Correct |
2561 ms |
4076 KB |
Output is correct |
8 |
Correct |
2476 ms |
4244 KB |
Output is correct |
9 |
Correct |
51 ms |
1508 KB |
Output is correct |
10 |
Correct |
1318 ms |
3968 KB |
Output is correct |
11 |
Correct |
1229 ms |
4256 KB |
Output is correct |
12 |
Correct |
1228 ms |
4420 KB |
Output is correct |
13 |
Correct |
1511 ms |
3608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1179 ms |
2804 KB |
Output is correct |
2 |
Correct |
895 ms |
1456 KB |
Output is correct |
3 |
Correct |
1371 ms |
2820 KB |
Output is correct |
4 |
Correct |
1164 ms |
2904 KB |
Output is correct |
5 |
Correct |
51 ms |
1636 KB |
Output is correct |
6 |
Correct |
1328 ms |
2732 KB |
Output is correct |
7 |
Correct |
1093 ms |
2648 KB |
Output is correct |
8 |
Correct |
946 ms |
2692 KB |
Output is correct |
9 |
Correct |
718 ms |
3400 KB |
Output is correct |
10 |
Correct |
658 ms |
3108 KB |
Output is correct |
11 |
Correct |
830 ms |
2564 KB |
Output is correct |
12 |
Correct |
726 ms |
2476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1610 ms |
7212 KB |
Output is correct |
2 |
Correct |
50 ms |
1508 KB |
Output is correct |
3 |
Correct |
204 ms |
5184 KB |
Output is correct |
4 |
Correct |
122 ms |
5184 KB |
Output is correct |
5 |
Correct |
993 ms |
7180 KB |
Output is correct |
6 |
Correct |
1589 ms |
7164 KB |
Output is correct |
7 |
Correct |
973 ms |
7264 KB |
Output is correct |
8 |
Correct |
827 ms |
4400 KB |
Output is correct |
9 |
Correct |
851 ms |
4356 KB |
Output is correct |
10 |
Correct |
826 ms |
4472 KB |
Output is correct |
11 |
Correct |
1246 ms |
6232 KB |
Output is correct |
12 |
Correct |
1215 ms |
6368 KB |
Output is correct |
13 |
Correct |
1258 ms |
6460 KB |
Output is correct |
14 |
Correct |
919 ms |
7316 KB |
Output is correct |
15 |
Correct |
975 ms |
7268 KB |
Output is correct |
16 |
Correct |
1624 ms |
7212 KB |
Output is correct |
17 |
Correct |
1632 ms |
7124 KB |
Output is correct |
18 |
Correct |
1642 ms |
7148 KB |
Output is correct |
19 |
Correct |
1616 ms |
7056 KB |
Output is correct |
20 |
Correct |
1389 ms |
6784 KB |
Output is correct |
21 |
Correct |
1389 ms |
6764 KB |
Output is correct |
22 |
Correct |
1589 ms |
7128 KB |
Output is correct |
23 |
Correct |
957 ms |
6612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1480 ms |
3876 KB |
Output is correct |
2 |
Correct |
1509 ms |
3888 KB |
Output is correct |
3 |
Correct |
1507 ms |
3992 KB |
Output is correct |
4 |
Correct |
1605 ms |
3972 KB |
Output is correct |
5 |
Correct |
1599 ms |
3976 KB |
Output is correct |
6 |
Correct |
2418 ms |
4200 KB |
Output is correct |
7 |
Correct |
2561 ms |
4076 KB |
Output is correct |
8 |
Correct |
2476 ms |
4244 KB |
Output is correct |
9 |
Correct |
51 ms |
1508 KB |
Output is correct |
10 |
Correct |
1318 ms |
3968 KB |
Output is correct |
11 |
Correct |
1229 ms |
4256 KB |
Output is correct |
12 |
Correct |
1228 ms |
4420 KB |
Output is correct |
13 |
Correct |
1511 ms |
3608 KB |
Output is correct |
14 |
Correct |
1179 ms |
2804 KB |
Output is correct |
15 |
Correct |
895 ms |
1456 KB |
Output is correct |
16 |
Correct |
1371 ms |
2820 KB |
Output is correct |
17 |
Correct |
1164 ms |
2904 KB |
Output is correct |
18 |
Correct |
51 ms |
1636 KB |
Output is correct |
19 |
Correct |
1328 ms |
2732 KB |
Output is correct |
20 |
Correct |
1093 ms |
2648 KB |
Output is correct |
21 |
Correct |
946 ms |
2692 KB |
Output is correct |
22 |
Correct |
718 ms |
3400 KB |
Output is correct |
23 |
Correct |
658 ms |
3108 KB |
Output is correct |
24 |
Correct |
830 ms |
2564 KB |
Output is correct |
25 |
Correct |
726 ms |
2476 KB |
Output is correct |
26 |
Correct |
1467 ms |
3936 KB |
Output is correct |
27 |
Correct |
1986 ms |
3912 KB |
Output is correct |
28 |
Correct |
1636 ms |
4024 KB |
Output is correct |
29 |
Correct |
1188 ms |
3832 KB |
Output is correct |
30 |
Correct |
1914 ms |
3924 KB |
Output is correct |
31 |
Correct |
1949 ms |
3916 KB |
Output is correct |
32 |
Correct |
1977 ms |
3916 KB |
Output is correct |
33 |
Correct |
1617 ms |
3876 KB |
Output is correct |
34 |
Correct |
1638 ms |
3804 KB |
Output is correct |
35 |
Correct |
1632 ms |
3784 KB |
Output is correct |
36 |
Correct |
1217 ms |
3884 KB |
Output is correct |
37 |
Correct |
1225 ms |
3916 KB |
Output is correct |
38 |
Correct |
1197 ms |
3892 KB |
Output is correct |
39 |
Correct |
957 ms |
4304 KB |
Output is correct |
40 |
Correct |
955 ms |
4332 KB |
Output is correct |
41 |
Correct |
955 ms |
4300 KB |
Output is correct |
42 |
Correct |
1026 ms |
3508 KB |
Output is correct |
43 |
Correct |
1041 ms |
3440 KB |
Output is correct |
44 |
Correct |
1048 ms |
3396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
252 KB |
Output is correct |
3 |
Correct |
40 ms |
504 KB |
Output is correct |
4 |
Correct |
7 ms |
632 KB |
Output is correct |
5 |
Correct |
17 ms |
504 KB |
Output is correct |
6 |
Correct |
18 ms |
504 KB |
Output is correct |
7 |
Correct |
20 ms |
504 KB |
Output is correct |
8 |
Correct |
21 ms |
504 KB |
Output is correct |
9 |
Correct |
22 ms |
504 KB |
Output is correct |
10 |
Correct |
22 ms |
504 KB |
Output is correct |
11 |
Correct |
22 ms |
504 KB |
Output is correct |
12 |
Correct |
24 ms |
504 KB |
Output is correct |
13 |
Correct |
29 ms |
504 KB |
Output is correct |
14 |
Correct |
27 ms |
504 KB |
Output is correct |
15 |
Correct |
24 ms |
636 KB |
Output is correct |
16 |
Correct |
21 ms |
504 KB |
Output is correct |
17 |
Correct |
21 ms |
504 KB |
Output is correct |
18 |
Correct |
1480 ms |
3876 KB |
Output is correct |
19 |
Correct |
1509 ms |
3888 KB |
Output is correct |
20 |
Correct |
1507 ms |
3992 KB |
Output is correct |
21 |
Correct |
1605 ms |
3972 KB |
Output is correct |
22 |
Correct |
1599 ms |
3976 KB |
Output is correct |
23 |
Correct |
2418 ms |
4200 KB |
Output is correct |
24 |
Correct |
2561 ms |
4076 KB |
Output is correct |
25 |
Correct |
2476 ms |
4244 KB |
Output is correct |
26 |
Correct |
51 ms |
1508 KB |
Output is correct |
27 |
Correct |
1318 ms |
3968 KB |
Output is correct |
28 |
Correct |
1229 ms |
4256 KB |
Output is correct |
29 |
Correct |
1228 ms |
4420 KB |
Output is correct |
30 |
Correct |
1511 ms |
3608 KB |
Output is correct |
31 |
Correct |
1179 ms |
2804 KB |
Output is correct |
32 |
Correct |
895 ms |
1456 KB |
Output is correct |
33 |
Correct |
1371 ms |
2820 KB |
Output is correct |
34 |
Correct |
1164 ms |
2904 KB |
Output is correct |
35 |
Correct |
51 ms |
1636 KB |
Output is correct |
36 |
Correct |
1328 ms |
2732 KB |
Output is correct |
37 |
Correct |
1093 ms |
2648 KB |
Output is correct |
38 |
Correct |
946 ms |
2692 KB |
Output is correct |
39 |
Correct |
718 ms |
3400 KB |
Output is correct |
40 |
Correct |
658 ms |
3108 KB |
Output is correct |
41 |
Correct |
830 ms |
2564 KB |
Output is correct |
42 |
Correct |
726 ms |
2476 KB |
Output is correct |
43 |
Correct |
1610 ms |
7212 KB |
Output is correct |
44 |
Correct |
50 ms |
1508 KB |
Output is correct |
45 |
Correct |
204 ms |
5184 KB |
Output is correct |
46 |
Correct |
122 ms |
5184 KB |
Output is correct |
47 |
Correct |
993 ms |
7180 KB |
Output is correct |
48 |
Correct |
1589 ms |
7164 KB |
Output is correct |
49 |
Correct |
973 ms |
7264 KB |
Output is correct |
50 |
Correct |
827 ms |
4400 KB |
Output is correct |
51 |
Correct |
851 ms |
4356 KB |
Output is correct |
52 |
Correct |
826 ms |
4472 KB |
Output is correct |
53 |
Correct |
1246 ms |
6232 KB |
Output is correct |
54 |
Correct |
1215 ms |
6368 KB |
Output is correct |
55 |
Correct |
1258 ms |
6460 KB |
Output is correct |
56 |
Correct |
919 ms |
7316 KB |
Output is correct |
57 |
Correct |
975 ms |
7268 KB |
Output is correct |
58 |
Correct |
1624 ms |
7212 KB |
Output is correct |
59 |
Correct |
1632 ms |
7124 KB |
Output is correct |
60 |
Correct |
1642 ms |
7148 KB |
Output is correct |
61 |
Correct |
1616 ms |
7056 KB |
Output is correct |
62 |
Correct |
1389 ms |
6784 KB |
Output is correct |
63 |
Correct |
1389 ms |
6764 KB |
Output is correct |
64 |
Correct |
1589 ms |
7128 KB |
Output is correct |
65 |
Correct |
957 ms |
6612 KB |
Output is correct |
66 |
Correct |
1467 ms |
3936 KB |
Output is correct |
67 |
Correct |
1986 ms |
3912 KB |
Output is correct |
68 |
Correct |
1636 ms |
4024 KB |
Output is correct |
69 |
Correct |
1188 ms |
3832 KB |
Output is correct |
70 |
Correct |
1914 ms |
3924 KB |
Output is correct |
71 |
Correct |
1949 ms |
3916 KB |
Output is correct |
72 |
Correct |
1977 ms |
3916 KB |
Output is correct |
73 |
Correct |
1617 ms |
3876 KB |
Output is correct |
74 |
Correct |
1638 ms |
3804 KB |
Output is correct |
75 |
Correct |
1632 ms |
3784 KB |
Output is correct |
76 |
Correct |
1217 ms |
3884 KB |
Output is correct |
77 |
Correct |
1225 ms |
3916 KB |
Output is correct |
78 |
Correct |
1197 ms |
3892 KB |
Output is correct |
79 |
Correct |
957 ms |
4304 KB |
Output is correct |
80 |
Correct |
955 ms |
4332 KB |
Output is correct |
81 |
Correct |
955 ms |
4300 KB |
Output is correct |
82 |
Correct |
1026 ms |
3508 KB |
Output is correct |
83 |
Correct |
1041 ms |
3440 KB |
Output is correct |
84 |
Correct |
1048 ms |
3396 KB |
Output is correct |
85 |
Correct |
2310 ms |
6276 KB |
Output is correct |
86 |
Correct |
249 ms |
5168 KB |
Output is correct |
87 |
Correct |
169 ms |
5160 KB |
Output is correct |
88 |
Correct |
1617 ms |
6448 KB |
Output is correct |
89 |
Correct |
2339 ms |
6296 KB |
Output is correct |
90 |
Correct |
1617 ms |
6364 KB |
Output is correct |
91 |
Correct |
1699 ms |
3876 KB |
Output is correct |
92 |
Correct |
1699 ms |
3836 KB |
Output is correct |
93 |
Correct |
2565 ms |
4084 KB |
Output is correct |
94 |
Correct |
2047 ms |
5528 KB |
Output is correct |
95 |
Correct |
2025 ms |
5664 KB |
Output is correct |
96 |
Correct |
2305 ms |
5524 KB |
Output is correct |
97 |
Correct |
1107 ms |
7164 KB |
Output is correct |
98 |
Correct |
1464 ms |
5816 KB |
Output is correct |
99 |
Correct |
2381 ms |
6448 KB |
Output is correct |
100 |
Correct |
2350 ms |
6332 KB |
Output is correct |
101 |
Correct |
2425 ms |
6316 KB |
Output is correct |
102 |
Correct |
2361 ms |
6280 KB |
Output is correct |
103 |
Correct |
2446 ms |
5824 KB |
Output is correct |
104 |
Correct |
2468 ms |
5892 KB |
Output is correct |
105 |
Correct |
1966 ms |
5412 KB |
Output is correct |
106 |
Correct |
1644 ms |
5012 KB |
Output is correct |
107 |
Correct |
1620 ms |
6768 KB |
Output is correct |
108 |
Correct |
2468 ms |
6260 KB |
Output is correct |
109 |
Correct |
1823 ms |
5788 KB |
Output is correct |