#include <bits/stdc++.h>
using namespace std;
const int BLOCK = 850;
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 |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
38 ms |
504 KB |
Output is correct |
4 |
Correct |
7 ms |
628 KB |
Output is correct |
5 |
Correct |
19 ms |
504 KB |
Output is correct |
6 |
Correct |
17 ms |
504 KB |
Output is correct |
7 |
Correct |
20 ms |
504 KB |
Output is correct |
8 |
Correct |
20 ms |
504 KB |
Output is correct |
9 |
Correct |
22 ms |
476 KB |
Output is correct |
10 |
Correct |
21 ms |
504 KB |
Output is correct |
11 |
Correct |
21 ms |
508 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 |
23 ms |
504 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 |
1474 ms |
3852 KB |
Output is correct |
2 |
Correct |
1516 ms |
3876 KB |
Output is correct |
3 |
Correct |
1517 ms |
3888 KB |
Output is correct |
4 |
Correct |
1584 ms |
3888 KB |
Output is correct |
5 |
Correct |
1565 ms |
3828 KB |
Output is correct |
6 |
Correct |
2378 ms |
4088 KB |
Output is correct |
7 |
Correct |
2377 ms |
4084 KB |
Output is correct |
8 |
Correct |
2377 ms |
4156 KB |
Output is correct |
9 |
Correct |
49 ms |
1508 KB |
Output is correct |
10 |
Correct |
1281 ms |
4012 KB |
Output is correct |
11 |
Correct |
1206 ms |
3916 KB |
Output is correct |
12 |
Correct |
1237 ms |
4488 KB |
Output is correct |
13 |
Correct |
1517 ms |
3544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1151 ms |
2688 KB |
Output is correct |
2 |
Correct |
850 ms |
1536 KB |
Output is correct |
3 |
Correct |
1359 ms |
2688 KB |
Output is correct |
4 |
Correct |
1127 ms |
2700 KB |
Output is correct |
5 |
Correct |
50 ms |
1508 KB |
Output is correct |
6 |
Correct |
1292 ms |
2748 KB |
Output is correct |
7 |
Correct |
1052 ms |
2672 KB |
Output is correct |
8 |
Correct |
938 ms |
2652 KB |
Output is correct |
9 |
Correct |
727 ms |
3164 KB |
Output is correct |
10 |
Correct |
669 ms |
3160 KB |
Output is correct |
11 |
Correct |
855 ms |
2324 KB |
Output is correct |
12 |
Correct |
753 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1701 ms |
7148 KB |
Output is correct |
2 |
Correct |
51 ms |
1512 KB |
Output is correct |
3 |
Correct |
202 ms |
5292 KB |
Output is correct |
4 |
Correct |
122 ms |
5184 KB |
Output is correct |
5 |
Correct |
1016 ms |
7276 KB |
Output is correct |
6 |
Correct |
1674 ms |
7124 KB |
Output is correct |
7 |
Correct |
1006 ms |
7440 KB |
Output is correct |
8 |
Correct |
862 ms |
4384 KB |
Output is correct |
9 |
Correct |
857 ms |
4300 KB |
Output is correct |
10 |
Correct |
866 ms |
4236 KB |
Output is correct |
11 |
Correct |
1294 ms |
6172 KB |
Output is correct |
12 |
Correct |
1273 ms |
6248 KB |
Output is correct |
13 |
Correct |
1315 ms |
6376 KB |
Output is correct |
14 |
Correct |
952 ms |
7284 KB |
Output is correct |
15 |
Correct |
992 ms |
7272 KB |
Output is correct |
16 |
Correct |
1694 ms |
7208 KB |
Output is correct |
17 |
Correct |
1720 ms |
7120 KB |
Output is correct |
18 |
Correct |
1703 ms |
7144 KB |
Output is correct |
19 |
Correct |
1692 ms |
7128 KB |
Output is correct |
20 |
Correct |
1458 ms |
6768 KB |
Output is correct |
21 |
Correct |
1462 ms |
6768 KB |
Output is correct |
22 |
Correct |
1637 ms |
7244 KB |
Output is correct |
23 |
Correct |
1014 ms |
6836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1474 ms |
3852 KB |
Output is correct |
2 |
Correct |
1516 ms |
3876 KB |
Output is correct |
3 |
Correct |
1517 ms |
3888 KB |
Output is correct |
4 |
Correct |
1584 ms |
3888 KB |
Output is correct |
5 |
Correct |
1565 ms |
3828 KB |
Output is correct |
6 |
Correct |
2378 ms |
4088 KB |
Output is correct |
7 |
Correct |
2377 ms |
4084 KB |
Output is correct |
8 |
Correct |
2377 ms |
4156 KB |
Output is correct |
9 |
Correct |
49 ms |
1508 KB |
Output is correct |
10 |
Correct |
1281 ms |
4012 KB |
Output is correct |
11 |
Correct |
1206 ms |
3916 KB |
Output is correct |
12 |
Correct |
1237 ms |
4488 KB |
Output is correct |
13 |
Correct |
1517 ms |
3544 KB |
Output is correct |
14 |
Correct |
1151 ms |
2688 KB |
Output is correct |
15 |
Correct |
850 ms |
1536 KB |
Output is correct |
16 |
Correct |
1359 ms |
2688 KB |
Output is correct |
17 |
Correct |
1127 ms |
2700 KB |
Output is correct |
18 |
Correct |
50 ms |
1508 KB |
Output is correct |
19 |
Correct |
1292 ms |
2748 KB |
Output is correct |
20 |
Correct |
1052 ms |
2672 KB |
Output is correct |
21 |
Correct |
938 ms |
2652 KB |
Output is correct |
22 |
Correct |
727 ms |
3164 KB |
Output is correct |
23 |
Correct |
669 ms |
3160 KB |
Output is correct |
24 |
Correct |
855 ms |
2324 KB |
Output is correct |
25 |
Correct |
753 ms |
2392 KB |
Output is correct |
26 |
Correct |
1462 ms |
3944 KB |
Output is correct |
27 |
Correct |
1933 ms |
4116 KB |
Output is correct |
28 |
Correct |
1639 ms |
4000 KB |
Output is correct |
29 |
Correct |
1204 ms |
3888 KB |
Output is correct |
30 |
Correct |
1885 ms |
3996 KB |
Output is correct |
31 |
Correct |
1907 ms |
4004 KB |
Output is correct |
32 |
Correct |
1979 ms |
3932 KB |
Output is correct |
33 |
Correct |
1593 ms |
3884 KB |
Output is correct |
34 |
Correct |
1606 ms |
3960 KB |
Output is correct |
35 |
Correct |
1614 ms |
3884 KB |
Output is correct |
36 |
Correct |
1242 ms |
3900 KB |
Output is correct |
37 |
Correct |
1243 ms |
3880 KB |
Output is correct |
38 |
Correct |
1216 ms |
3836 KB |
Output is correct |
39 |
Correct |
1008 ms |
4296 KB |
Output is correct |
40 |
Correct |
985 ms |
4300 KB |
Output is correct |
41 |
Correct |
1010 ms |
4324 KB |
Output is correct |
42 |
Correct |
1054 ms |
3656 KB |
Output is correct |
43 |
Correct |
1111 ms |
3624 KB |
Output is correct |
44 |
Correct |
1049 ms |
3492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
38 ms |
504 KB |
Output is correct |
4 |
Correct |
7 ms |
628 KB |
Output is correct |
5 |
Correct |
19 ms |
504 KB |
Output is correct |
6 |
Correct |
17 ms |
504 KB |
Output is correct |
7 |
Correct |
20 ms |
504 KB |
Output is correct |
8 |
Correct |
20 ms |
504 KB |
Output is correct |
9 |
Correct |
22 ms |
476 KB |
Output is correct |
10 |
Correct |
21 ms |
504 KB |
Output is correct |
11 |
Correct |
21 ms |
508 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 |
23 ms |
504 KB |
Output is correct |
16 |
Correct |
21 ms |
504 KB |
Output is correct |
17 |
Correct |
21 ms |
504 KB |
Output is correct |
18 |
Correct |
1474 ms |
3852 KB |
Output is correct |
19 |
Correct |
1516 ms |
3876 KB |
Output is correct |
20 |
Correct |
1517 ms |
3888 KB |
Output is correct |
21 |
Correct |
1584 ms |
3888 KB |
Output is correct |
22 |
Correct |
1565 ms |
3828 KB |
Output is correct |
23 |
Correct |
2378 ms |
4088 KB |
Output is correct |
24 |
Correct |
2377 ms |
4084 KB |
Output is correct |
25 |
Correct |
2377 ms |
4156 KB |
Output is correct |
26 |
Correct |
49 ms |
1508 KB |
Output is correct |
27 |
Correct |
1281 ms |
4012 KB |
Output is correct |
28 |
Correct |
1206 ms |
3916 KB |
Output is correct |
29 |
Correct |
1237 ms |
4488 KB |
Output is correct |
30 |
Correct |
1517 ms |
3544 KB |
Output is correct |
31 |
Correct |
1151 ms |
2688 KB |
Output is correct |
32 |
Correct |
850 ms |
1536 KB |
Output is correct |
33 |
Correct |
1359 ms |
2688 KB |
Output is correct |
34 |
Correct |
1127 ms |
2700 KB |
Output is correct |
35 |
Correct |
50 ms |
1508 KB |
Output is correct |
36 |
Correct |
1292 ms |
2748 KB |
Output is correct |
37 |
Correct |
1052 ms |
2672 KB |
Output is correct |
38 |
Correct |
938 ms |
2652 KB |
Output is correct |
39 |
Correct |
727 ms |
3164 KB |
Output is correct |
40 |
Correct |
669 ms |
3160 KB |
Output is correct |
41 |
Correct |
855 ms |
2324 KB |
Output is correct |
42 |
Correct |
753 ms |
2392 KB |
Output is correct |
43 |
Correct |
1701 ms |
7148 KB |
Output is correct |
44 |
Correct |
51 ms |
1512 KB |
Output is correct |
45 |
Correct |
202 ms |
5292 KB |
Output is correct |
46 |
Correct |
122 ms |
5184 KB |
Output is correct |
47 |
Correct |
1016 ms |
7276 KB |
Output is correct |
48 |
Correct |
1674 ms |
7124 KB |
Output is correct |
49 |
Correct |
1006 ms |
7440 KB |
Output is correct |
50 |
Correct |
862 ms |
4384 KB |
Output is correct |
51 |
Correct |
857 ms |
4300 KB |
Output is correct |
52 |
Correct |
866 ms |
4236 KB |
Output is correct |
53 |
Correct |
1294 ms |
6172 KB |
Output is correct |
54 |
Correct |
1273 ms |
6248 KB |
Output is correct |
55 |
Correct |
1315 ms |
6376 KB |
Output is correct |
56 |
Correct |
952 ms |
7284 KB |
Output is correct |
57 |
Correct |
992 ms |
7272 KB |
Output is correct |
58 |
Correct |
1694 ms |
7208 KB |
Output is correct |
59 |
Correct |
1720 ms |
7120 KB |
Output is correct |
60 |
Correct |
1703 ms |
7144 KB |
Output is correct |
61 |
Correct |
1692 ms |
7128 KB |
Output is correct |
62 |
Correct |
1458 ms |
6768 KB |
Output is correct |
63 |
Correct |
1462 ms |
6768 KB |
Output is correct |
64 |
Correct |
1637 ms |
7244 KB |
Output is correct |
65 |
Correct |
1014 ms |
6836 KB |
Output is correct |
66 |
Correct |
1462 ms |
3944 KB |
Output is correct |
67 |
Correct |
1933 ms |
4116 KB |
Output is correct |
68 |
Correct |
1639 ms |
4000 KB |
Output is correct |
69 |
Correct |
1204 ms |
3888 KB |
Output is correct |
70 |
Correct |
1885 ms |
3996 KB |
Output is correct |
71 |
Correct |
1907 ms |
4004 KB |
Output is correct |
72 |
Correct |
1979 ms |
3932 KB |
Output is correct |
73 |
Correct |
1593 ms |
3884 KB |
Output is correct |
74 |
Correct |
1606 ms |
3960 KB |
Output is correct |
75 |
Correct |
1614 ms |
3884 KB |
Output is correct |
76 |
Correct |
1242 ms |
3900 KB |
Output is correct |
77 |
Correct |
1243 ms |
3880 KB |
Output is correct |
78 |
Correct |
1216 ms |
3836 KB |
Output is correct |
79 |
Correct |
1008 ms |
4296 KB |
Output is correct |
80 |
Correct |
985 ms |
4300 KB |
Output is correct |
81 |
Correct |
1010 ms |
4324 KB |
Output is correct |
82 |
Correct |
1054 ms |
3656 KB |
Output is correct |
83 |
Correct |
1111 ms |
3624 KB |
Output is correct |
84 |
Correct |
1049 ms |
3492 KB |
Output is correct |
85 |
Correct |
2359 ms |
6364 KB |
Output is correct |
86 |
Correct |
248 ms |
5184 KB |
Output is correct |
87 |
Correct |
168 ms |
5308 KB |
Output is correct |
88 |
Correct |
1639 ms |
6448 KB |
Output is correct |
89 |
Correct |
2342 ms |
6464 KB |
Output is correct |
90 |
Correct |
1635 ms |
6496 KB |
Output is correct |
91 |
Correct |
1684 ms |
3988 KB |
Output is correct |
92 |
Correct |
1692 ms |
3856 KB |
Output is correct |
93 |
Correct |
2468 ms |
4056 KB |
Output is correct |
94 |
Correct |
2070 ms |
5412 KB |
Output is correct |
95 |
Correct |
2029 ms |
5480 KB |
Output is correct |
96 |
Correct |
2301 ms |
5552 KB |
Output is correct |
97 |
Correct |
1142 ms |
7152 KB |
Output is correct |
98 |
Correct |
1459 ms |
5904 KB |
Output is correct |
99 |
Correct |
2405 ms |
6396 KB |
Output is correct |
100 |
Correct |
2489 ms |
6320 KB |
Output is correct |
101 |
Correct |
2427 ms |
6428 KB |
Output is correct |
102 |
Correct |
2421 ms |
6400 KB |
Output is correct |
103 |
Correct |
2481 ms |
5984 KB |
Output is correct |
104 |
Correct |
2472 ms |
6112 KB |
Output is correct |
105 |
Correct |
2083 ms |
5304 KB |
Output is correct |
106 |
Correct |
1735 ms |
4944 KB |
Output is correct |
107 |
Correct |
1648 ms |
6808 KB |
Output is correct |
108 |
Correct |
2496 ms |
6388 KB |
Output is correct |
109 |
Correct |
1830 ms |
5808 KB |
Output is correct |