#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define eb(x...) emplace_back(x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) int((x).size())
const int N = 1 << 16, M = 1 << 17, Q = M, B = 1 << 10;
int nxt[N], sz[N]; stack<int> save;
int head(int u) { return nxt[u] < 0 ? u : head(nxt[u]); }
void unite(int u, int v) {
u = head(u); v = head(v);
if (u == v) return save.push(-1);
if (sz[u] > sz[v]) swap(u, v);
nxt[u] = v; sz[v] += sz[u]; save.push(u);
}
void rollback() {
int u = save.top(); save.pop();
if (u < 0) return;
sz[nxt[u]] -= sz[u]; nxt[u] = -1;
}
int u[M], v[M], w[M], ord[M];
short t[Q]; int b[Q], c[Q];
int ans[Q];
bool changed[M];
vector<int> changed_edges;
vector<tuple<int, int, int>> queries;
vector<pair<int, int>> weights[M];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
rep(e, 0, m) cin >> u[e] >> v[e] >> w[e], --u[e], --v[e];
int q; cin >> q;
rep(i, 0, q) cin >> t[i] >> b[i] >> c[i], --b[i], --t[i];
for (int l = 0, r = 0; r = min(l + B, q), l < q; l += B) {
fill(nxt, nxt + n, -1); fill(sz, sz + n, 1);
fill(changed, changed + m, false); changed_edges.clear();
queries.clear();
iota(ord, ord + m, 0); sort(ord, ord + m, [&](int x, int y) { return w[x] > w[y]; });
rep(i, l, r)
if (t[i]) queries.eb(c[i], b[i], i);
else changed[b[i]] = true;
rep(e, 0, m) if (changed[e]) weights[e] = {{w[e], 0}}, changed_edges.eb(e);
rep(i, l, r) if (!t[i]) weights[b[i]].eb(c[i], i);
sort(rall(queries));
int e = 0;
for (auto &[z, s, t] : queries) {
while (e < m && z <= w[ord[e]]) { if (!changed[ord[e]]) unite(u[ord[e]], v[ord[e]]); ++e; }
int dsu_changes = 0;
for (auto e : changed_edges) {
int c = 0;
while (c < sz(weights[e]) && weights[e][c].second <= t) ++c;
--c; if (z <= weights[e][c].first) unite(u[e], v[e]), ++dsu_changes;
}
ans[t] = sz[head(s)];
while (dsu_changes--) rollback();
}
rep(i, l, r) if (!t[i]) w[b[i]] = c[i];
}
rep(i, 0, q) if (t[i]) cout << ans[i] << '\n';
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
62 | for (auto &[z, s, t] : queries) {
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3436 KB |
Output is correct |
2 |
Correct |
2 ms |
3436 KB |
Output is correct |
3 |
Correct |
49 ms |
3692 KB |
Output is correct |
4 |
Correct |
6 ms |
3692 KB |
Output is correct |
5 |
Correct |
19 ms |
3692 KB |
Output is correct |
6 |
Correct |
17 ms |
3692 KB |
Output is correct |
7 |
Correct |
19 ms |
3692 KB |
Output is correct |
8 |
Correct |
19 ms |
3692 KB |
Output is correct |
9 |
Correct |
20 ms |
3692 KB |
Output is correct |
10 |
Correct |
19 ms |
3692 KB |
Output is correct |
11 |
Correct |
18 ms |
3692 KB |
Output is correct |
12 |
Correct |
20 ms |
3692 KB |
Output is correct |
13 |
Correct |
27 ms |
3720 KB |
Output is correct |
14 |
Correct |
25 ms |
3692 KB |
Output is correct |
15 |
Correct |
21 ms |
3692 KB |
Output is correct |
16 |
Correct |
20 ms |
3692 KB |
Output is correct |
17 |
Correct |
20 ms |
3692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1549 ms |
27288 KB |
Output is correct |
2 |
Correct |
1560 ms |
27040 KB |
Output is correct |
3 |
Correct |
1570 ms |
27060 KB |
Output is correct |
4 |
Correct |
1527 ms |
26992 KB |
Output is correct |
5 |
Correct |
1523 ms |
27336 KB |
Output is correct |
6 |
Correct |
2139 ms |
27296 KB |
Output is correct |
7 |
Correct |
2107 ms |
27312 KB |
Output is correct |
8 |
Correct |
2141 ms |
27308 KB |
Output is correct |
9 |
Correct |
40 ms |
5100 KB |
Output is correct |
10 |
Correct |
1290 ms |
27272 KB |
Output is correct |
11 |
Correct |
1231 ms |
27168 KB |
Output is correct |
12 |
Correct |
1232 ms |
27040 KB |
Output is correct |
13 |
Correct |
1276 ms |
27300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1263 ms |
19580 KB |
Output is correct |
2 |
Correct |
904 ms |
8692 KB |
Output is correct |
3 |
Correct |
1405 ms |
19836 KB |
Output is correct |
4 |
Correct |
1240 ms |
19708 KB |
Output is correct |
5 |
Correct |
40 ms |
5100 KB |
Output is correct |
6 |
Correct |
1357 ms |
19836 KB |
Output is correct |
7 |
Correct |
1162 ms |
19768 KB |
Output is correct |
8 |
Correct |
1041 ms |
19708 KB |
Output is correct |
9 |
Correct |
756 ms |
19580 KB |
Output is correct |
10 |
Correct |
697 ms |
19324 KB |
Output is correct |
11 |
Correct |
834 ms |
19452 KB |
Output is correct |
12 |
Correct |
774 ms |
19452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1670 ms |
47576 KB |
Output is correct |
2 |
Correct |
40 ms |
5100 KB |
Output is correct |
3 |
Correct |
178 ms |
9452 KB |
Output is correct |
4 |
Correct |
89 ms |
9452 KB |
Output is correct |
5 |
Correct |
830 ms |
47728 KB |
Output is correct |
6 |
Correct |
1627 ms |
47600 KB |
Output is correct |
7 |
Correct |
825 ms |
47872 KB |
Output is correct |
8 |
Correct |
768 ms |
26596 KB |
Output is correct |
9 |
Correct |
752 ms |
26392 KB |
Output is correct |
10 |
Correct |
761 ms |
26640 KB |
Output is correct |
11 |
Correct |
1210 ms |
36976 KB |
Output is correct |
12 |
Correct |
1192 ms |
36880 KB |
Output is correct |
13 |
Correct |
1225 ms |
37232 KB |
Output is correct |
14 |
Correct |
758 ms |
47736 KB |
Output is correct |
15 |
Correct |
800 ms |
47728 KB |
Output is correct |
16 |
Correct |
1656 ms |
47328 KB |
Output is correct |
17 |
Correct |
1664 ms |
47472 KB |
Output is correct |
18 |
Correct |
1656 ms |
47472 KB |
Output is correct |
19 |
Correct |
1658 ms |
47344 KB |
Output is correct |
20 |
Correct |
1379 ms |
40816 KB |
Output is correct |
21 |
Correct |
1378 ms |
40832 KB |
Output is correct |
22 |
Correct |
1595 ms |
45844 KB |
Output is correct |
23 |
Correct |
923 ms |
39536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1549 ms |
27288 KB |
Output is correct |
2 |
Correct |
1560 ms |
27040 KB |
Output is correct |
3 |
Correct |
1570 ms |
27060 KB |
Output is correct |
4 |
Correct |
1527 ms |
26992 KB |
Output is correct |
5 |
Correct |
1523 ms |
27336 KB |
Output is correct |
6 |
Correct |
2139 ms |
27296 KB |
Output is correct |
7 |
Correct |
2107 ms |
27312 KB |
Output is correct |
8 |
Correct |
2141 ms |
27308 KB |
Output is correct |
9 |
Correct |
40 ms |
5100 KB |
Output is correct |
10 |
Correct |
1290 ms |
27272 KB |
Output is correct |
11 |
Correct |
1231 ms |
27168 KB |
Output is correct |
12 |
Correct |
1232 ms |
27040 KB |
Output is correct |
13 |
Correct |
1276 ms |
27300 KB |
Output is correct |
14 |
Correct |
1263 ms |
19580 KB |
Output is correct |
15 |
Correct |
904 ms |
8692 KB |
Output is correct |
16 |
Correct |
1405 ms |
19836 KB |
Output is correct |
17 |
Correct |
1240 ms |
19708 KB |
Output is correct |
18 |
Correct |
40 ms |
5100 KB |
Output is correct |
19 |
Correct |
1357 ms |
19836 KB |
Output is correct |
20 |
Correct |
1162 ms |
19768 KB |
Output is correct |
21 |
Correct |
1041 ms |
19708 KB |
Output is correct |
22 |
Correct |
756 ms |
19580 KB |
Output is correct |
23 |
Correct |
697 ms |
19324 KB |
Output is correct |
24 |
Correct |
834 ms |
19452 KB |
Output is correct |
25 |
Correct |
774 ms |
19452 KB |
Output is correct |
26 |
Correct |
1643 ms |
27304 KB |
Output is correct |
27 |
Correct |
1996 ms |
27208 KB |
Output is correct |
28 |
Correct |
1686 ms |
27612 KB |
Output is correct |
29 |
Correct |
1260 ms |
27008 KB |
Output is correct |
30 |
Correct |
1870 ms |
27424 KB |
Output is correct |
31 |
Correct |
1915 ms |
27424 KB |
Output is correct |
32 |
Correct |
1930 ms |
27296 KB |
Output is correct |
33 |
Correct |
1639 ms |
27296 KB |
Output is correct |
34 |
Correct |
1652 ms |
27196 KB |
Output is correct |
35 |
Correct |
1663 ms |
27168 KB |
Output is correct |
36 |
Correct |
1312 ms |
27092 KB |
Output is correct |
37 |
Correct |
1288 ms |
27228 KB |
Output is correct |
38 |
Correct |
1276 ms |
27040 KB |
Output is correct |
39 |
Correct |
929 ms |
26656 KB |
Output is correct |
40 |
Correct |
928 ms |
26660 KB |
Output is correct |
41 |
Correct |
922 ms |
26528 KB |
Output is correct |
42 |
Correct |
976 ms |
26528 KB |
Output is correct |
43 |
Correct |
979 ms |
26784 KB |
Output is correct |
44 |
Correct |
975 ms |
26528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3436 KB |
Output is correct |
2 |
Correct |
2 ms |
3436 KB |
Output is correct |
3 |
Correct |
49 ms |
3692 KB |
Output is correct |
4 |
Correct |
6 ms |
3692 KB |
Output is correct |
5 |
Correct |
19 ms |
3692 KB |
Output is correct |
6 |
Correct |
17 ms |
3692 KB |
Output is correct |
7 |
Correct |
19 ms |
3692 KB |
Output is correct |
8 |
Correct |
19 ms |
3692 KB |
Output is correct |
9 |
Correct |
20 ms |
3692 KB |
Output is correct |
10 |
Correct |
19 ms |
3692 KB |
Output is correct |
11 |
Correct |
18 ms |
3692 KB |
Output is correct |
12 |
Correct |
20 ms |
3692 KB |
Output is correct |
13 |
Correct |
27 ms |
3720 KB |
Output is correct |
14 |
Correct |
25 ms |
3692 KB |
Output is correct |
15 |
Correct |
21 ms |
3692 KB |
Output is correct |
16 |
Correct |
20 ms |
3692 KB |
Output is correct |
17 |
Correct |
20 ms |
3692 KB |
Output is correct |
18 |
Correct |
1549 ms |
27288 KB |
Output is correct |
19 |
Correct |
1560 ms |
27040 KB |
Output is correct |
20 |
Correct |
1570 ms |
27060 KB |
Output is correct |
21 |
Correct |
1527 ms |
26992 KB |
Output is correct |
22 |
Correct |
1523 ms |
27336 KB |
Output is correct |
23 |
Correct |
2139 ms |
27296 KB |
Output is correct |
24 |
Correct |
2107 ms |
27312 KB |
Output is correct |
25 |
Correct |
2141 ms |
27308 KB |
Output is correct |
26 |
Correct |
40 ms |
5100 KB |
Output is correct |
27 |
Correct |
1290 ms |
27272 KB |
Output is correct |
28 |
Correct |
1231 ms |
27168 KB |
Output is correct |
29 |
Correct |
1232 ms |
27040 KB |
Output is correct |
30 |
Correct |
1276 ms |
27300 KB |
Output is correct |
31 |
Correct |
1263 ms |
19580 KB |
Output is correct |
32 |
Correct |
904 ms |
8692 KB |
Output is correct |
33 |
Correct |
1405 ms |
19836 KB |
Output is correct |
34 |
Correct |
1240 ms |
19708 KB |
Output is correct |
35 |
Correct |
40 ms |
5100 KB |
Output is correct |
36 |
Correct |
1357 ms |
19836 KB |
Output is correct |
37 |
Correct |
1162 ms |
19768 KB |
Output is correct |
38 |
Correct |
1041 ms |
19708 KB |
Output is correct |
39 |
Correct |
756 ms |
19580 KB |
Output is correct |
40 |
Correct |
697 ms |
19324 KB |
Output is correct |
41 |
Correct |
834 ms |
19452 KB |
Output is correct |
42 |
Correct |
774 ms |
19452 KB |
Output is correct |
43 |
Correct |
1670 ms |
47576 KB |
Output is correct |
44 |
Correct |
40 ms |
5100 KB |
Output is correct |
45 |
Correct |
178 ms |
9452 KB |
Output is correct |
46 |
Correct |
89 ms |
9452 KB |
Output is correct |
47 |
Correct |
830 ms |
47728 KB |
Output is correct |
48 |
Correct |
1627 ms |
47600 KB |
Output is correct |
49 |
Correct |
825 ms |
47872 KB |
Output is correct |
50 |
Correct |
768 ms |
26596 KB |
Output is correct |
51 |
Correct |
752 ms |
26392 KB |
Output is correct |
52 |
Correct |
761 ms |
26640 KB |
Output is correct |
53 |
Correct |
1210 ms |
36976 KB |
Output is correct |
54 |
Correct |
1192 ms |
36880 KB |
Output is correct |
55 |
Correct |
1225 ms |
37232 KB |
Output is correct |
56 |
Correct |
758 ms |
47736 KB |
Output is correct |
57 |
Correct |
800 ms |
47728 KB |
Output is correct |
58 |
Correct |
1656 ms |
47328 KB |
Output is correct |
59 |
Correct |
1664 ms |
47472 KB |
Output is correct |
60 |
Correct |
1656 ms |
47472 KB |
Output is correct |
61 |
Correct |
1658 ms |
47344 KB |
Output is correct |
62 |
Correct |
1379 ms |
40816 KB |
Output is correct |
63 |
Correct |
1378 ms |
40832 KB |
Output is correct |
64 |
Correct |
1595 ms |
45844 KB |
Output is correct |
65 |
Correct |
923 ms |
39536 KB |
Output is correct |
66 |
Correct |
1643 ms |
27304 KB |
Output is correct |
67 |
Correct |
1996 ms |
27208 KB |
Output is correct |
68 |
Correct |
1686 ms |
27612 KB |
Output is correct |
69 |
Correct |
1260 ms |
27008 KB |
Output is correct |
70 |
Correct |
1870 ms |
27424 KB |
Output is correct |
71 |
Correct |
1915 ms |
27424 KB |
Output is correct |
72 |
Correct |
1930 ms |
27296 KB |
Output is correct |
73 |
Correct |
1639 ms |
27296 KB |
Output is correct |
74 |
Correct |
1652 ms |
27196 KB |
Output is correct |
75 |
Correct |
1663 ms |
27168 KB |
Output is correct |
76 |
Correct |
1312 ms |
27092 KB |
Output is correct |
77 |
Correct |
1288 ms |
27228 KB |
Output is correct |
78 |
Correct |
1276 ms |
27040 KB |
Output is correct |
79 |
Correct |
929 ms |
26656 KB |
Output is correct |
80 |
Correct |
928 ms |
26660 KB |
Output is correct |
81 |
Correct |
922 ms |
26528 KB |
Output is correct |
82 |
Correct |
976 ms |
26528 KB |
Output is correct |
83 |
Correct |
979 ms |
26784 KB |
Output is correct |
84 |
Correct |
975 ms |
26528 KB |
Output is correct |
85 |
Correct |
2552 ms |
48324 KB |
Output is correct |
86 |
Correct |
244 ms |
9512 KB |
Output is correct |
87 |
Correct |
172 ms |
9452 KB |
Output is correct |
88 |
Correct |
1707 ms |
48496 KB |
Output is correct |
89 |
Correct |
2548 ms |
48348 KB |
Output is correct |
90 |
Correct |
1716 ms |
48368 KB |
Output is correct |
91 |
Correct |
1701 ms |
27420 KB |
Output is correct |
92 |
Correct |
1684 ms |
27112 KB |
Output is correct |
93 |
Correct |
2310 ms |
27204 KB |
Output is correct |
94 |
Correct |
2181 ms |
37872 KB |
Output is correct |
95 |
Correct |
2137 ms |
37616 KB |
Output is correct |
96 |
Correct |
2545 ms |
37744 KB |
Output is correct |
97 |
Correct |
1086 ms |
47856 KB |
Output is correct |
98 |
Correct |
1241 ms |
48240 KB |
Output is correct |
99 |
Correct |
2591 ms |
47984 KB |
Output is correct |
100 |
Correct |
2611 ms |
47796 KB |
Output is correct |
101 |
Correct |
2595 ms |
48112 KB |
Output is correct |
102 |
Correct |
2592 ms |
48112 KB |
Output is correct |
103 |
Correct |
2756 ms |
41328 KB |
Output is correct |
104 |
Correct |
2745 ms |
41200 KB |
Output is correct |
105 |
Correct |
1950 ms |
44660 KB |
Output is correct |
106 |
Correct |
1530 ms |
40944 KB |
Output is correct |
107 |
Correct |
1806 ms |
44144 KB |
Output is correct |
108 |
Correct |
2709 ms |
49880 KB |
Output is correct |
109 |
Correct |
2025 ms |
41840 KB |
Output is correct |