#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];
int head(int u) { return nxt[u] < 0 ? u : nxt[u] = head(nxt[u]); }
void unite(int u, int v) {
u = head(u); v = head(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
nxt[u] = v; sz[v] += sz[u];
}
int u[M], v[M], w[M];
short t[Q]; int b[Q], c[Q], ans[Q];
bool changed[M];
vector<int> changed_nodes, g[N];
vector<tuple<int, int, int>> queries;
vector<pair<int, int>> weights[M];
bool vis[N];
vector<int> ord, changed_edges;
void dfs(int u) { vis[u] = 1; for (int v : g[u]) if (!vis[v]) dfs(v); }
bool cmp(int x, int y) { return w[x] > w[y]; }
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];
ord.resize(m); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), cmp);
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();
rep(i, l, r)
if (t[i]) queries.eb(c[i], b[i], i);
else changed[b[i]] = true;
auto second = stable_partition(ord.begin(), ord.end(), [](int x) { return !changed[x]; });
for_each(second, ord.end(), [](int x) {
weights[x] = {{w[x], 0}};
changed_edges.push_back(x);
});
ord.erase(second, ord.end());
rep(i, l, r) if (!t[i]) weights[b[i]].eb(c[i], i);
sort(rall(queries));
auto it = begin(ord);
for (auto &[z, s, t] : queries) {
while (it != end(ord) && z <= w[*it]) { unite(u[*it], v[*it]); ++it; }
for (auto e : changed_edges) {
int c = 0;
while (c < sz(weights[e]) && weights[e][c].second <= t) ++c;
if (z <= weights[e][--c].first) {
int x = head(u[e]), y = head(v[e]);
g[x].eb(y); g[y].eb(x);
changed_nodes.eb(x); changed_nodes.eb(y);
}
}
dfs(s = head(s)); vis[s] = 0; ans[t] = sz[s];
for (int x : changed_nodes) {
if (vis[x]) ans[t] += sz[x];
g[x].clear(), vis[x] = 0;
}
changed_nodes.clear();
}
rep(i, l, r) if (!t[i]) w[b[i]] = c[i];
sort(begin(changed_edges), end(changed_edges), cmp);
vector<int> tmp(ord.size()+changed_edges.size());
merge(ord.begin(), ord.end(), changed_edges.begin(), changed_edges.end(), tmp.begin(), cmp);
ord = move(tmp);
}
rep(i, 0, q) if (t[i]) cout << ans[i] << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
3 ms |
4992 KB |
Output is correct |
3 |
Correct |
83 ms |
5368 KB |
Output is correct |
4 |
Correct |
8 ms |
5120 KB |
Output is correct |
5 |
Correct |
28 ms |
5248 KB |
Output is correct |
6 |
Correct |
25 ms |
5248 KB |
Output is correct |
7 |
Correct |
29 ms |
5240 KB |
Output is correct |
8 |
Correct |
29 ms |
5240 KB |
Output is correct |
9 |
Correct |
37 ms |
5240 KB |
Output is correct |
10 |
Correct |
27 ms |
5244 KB |
Output is correct |
11 |
Correct |
26 ms |
5240 KB |
Output is correct |
12 |
Correct |
28 ms |
5248 KB |
Output is correct |
13 |
Correct |
37 ms |
5240 KB |
Output is correct |
14 |
Correct |
35 ms |
5248 KB |
Output is correct |
15 |
Correct |
36 ms |
5240 KB |
Output is correct |
16 |
Correct |
31 ms |
5240 KB |
Output is correct |
17 |
Correct |
30 ms |
5240 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1828 ms |
10472 KB |
Output is correct |
2 |
Correct |
1798 ms |
10256 KB |
Output is correct |
3 |
Correct |
1623 ms |
10408 KB |
Output is correct |
4 |
Correct |
1521 ms |
10328 KB |
Output is correct |
5 |
Correct |
1605 ms |
10356 KB |
Output is correct |
6 |
Correct |
2904 ms |
9608 KB |
Output is correct |
7 |
Correct |
2922 ms |
12204 KB |
Output is correct |
8 |
Correct |
2535 ms |
12212 KB |
Output is correct |
9 |
Correct |
49 ms |
7928 KB |
Output is correct |
10 |
Correct |
2157 ms |
12008 KB |
Output is correct |
11 |
Correct |
1882 ms |
12096 KB |
Output is correct |
12 |
Correct |
1170 ms |
11232 KB |
Output is correct |
13 |
Correct |
1344 ms |
12812 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1461 ms |
9432 KB |
Output is correct |
2 |
Correct |
1649 ms |
7428 KB |
Output is correct |
3 |
Correct |
2016 ms |
9628 KB |
Output is correct |
4 |
Correct |
1845 ms |
9388 KB |
Output is correct |
5 |
Correct |
49 ms |
6520 KB |
Output is correct |
6 |
Correct |
1712 ms |
9308 KB |
Output is correct |
7 |
Correct |
1761 ms |
9372 KB |
Output is correct |
8 |
Correct |
1059 ms |
9404 KB |
Output is correct |
9 |
Correct |
934 ms |
8424 KB |
Output is correct |
10 |
Correct |
627 ms |
8320 KB |
Output is correct |
11 |
Correct |
960 ms |
9572 KB |
Output is correct |
12 |
Correct |
800 ms |
9600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
508 ms |
9388 KB |
Output is correct |
2 |
Correct |
50 ms |
6520 KB |
Output is correct |
3 |
Correct |
83 ms |
7360 KB |
Output is correct |
4 |
Correct |
59 ms |
7272 KB |
Output is correct |
5 |
Correct |
371 ms |
9432 KB |
Output is correct |
6 |
Correct |
506 ms |
9308 KB |
Output is correct |
7 |
Correct |
366 ms |
9564 KB |
Output is correct |
8 |
Correct |
283 ms |
8164 KB |
Output is correct |
9 |
Correct |
288 ms |
8036 KB |
Output is correct |
10 |
Correct |
286 ms |
8420 KB |
Output is correct |
11 |
Correct |
465 ms |
8600 KB |
Output is correct |
12 |
Correct |
453 ms |
8860 KB |
Output is correct |
13 |
Correct |
455 ms |
8872 KB |
Output is correct |
14 |
Correct |
362 ms |
9440 KB |
Output is correct |
15 |
Correct |
366 ms |
9436 KB |
Output is correct |
16 |
Correct |
561 ms |
9316 KB |
Output is correct |
17 |
Correct |
589 ms |
9444 KB |
Output is correct |
18 |
Correct |
552 ms |
9432 KB |
Output is correct |
19 |
Correct |
563 ms |
9312 KB |
Output is correct |
20 |
Correct |
517 ms |
9088 KB |
Output is correct |
21 |
Correct |
524 ms |
9440 KB |
Output is correct |
22 |
Correct |
537 ms |
9348 KB |
Output is correct |
23 |
Correct |
440 ms |
9076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1828 ms |
10472 KB |
Output is correct |
2 |
Correct |
1798 ms |
10256 KB |
Output is correct |
3 |
Correct |
1623 ms |
10408 KB |
Output is correct |
4 |
Correct |
1521 ms |
10328 KB |
Output is correct |
5 |
Correct |
1605 ms |
10356 KB |
Output is correct |
6 |
Correct |
2904 ms |
9608 KB |
Output is correct |
7 |
Correct |
2922 ms |
12204 KB |
Output is correct |
8 |
Correct |
2535 ms |
12212 KB |
Output is correct |
9 |
Correct |
49 ms |
7928 KB |
Output is correct |
10 |
Correct |
2157 ms |
12008 KB |
Output is correct |
11 |
Correct |
1882 ms |
12096 KB |
Output is correct |
12 |
Correct |
1170 ms |
11232 KB |
Output is correct |
13 |
Correct |
1344 ms |
12812 KB |
Output is correct |
14 |
Correct |
1461 ms |
9432 KB |
Output is correct |
15 |
Correct |
1649 ms |
7428 KB |
Output is correct |
16 |
Correct |
2016 ms |
9628 KB |
Output is correct |
17 |
Correct |
1845 ms |
9388 KB |
Output is correct |
18 |
Correct |
49 ms |
6520 KB |
Output is correct |
19 |
Correct |
1712 ms |
9308 KB |
Output is correct |
20 |
Correct |
1761 ms |
9372 KB |
Output is correct |
21 |
Correct |
1059 ms |
9404 KB |
Output is correct |
22 |
Correct |
934 ms |
8424 KB |
Output is correct |
23 |
Correct |
627 ms |
8320 KB |
Output is correct |
24 |
Correct |
960 ms |
9572 KB |
Output is correct |
25 |
Correct |
800 ms |
9600 KB |
Output is correct |
26 |
Correct |
1697 ms |
13428 KB |
Output is correct |
27 |
Correct |
2249 ms |
13572 KB |
Output is correct |
28 |
Correct |
1715 ms |
13292 KB |
Output is correct |
29 |
Correct |
1018 ms |
13064 KB |
Output is correct |
30 |
Correct |
2232 ms |
13420 KB |
Output is correct |
31 |
Correct |
2185 ms |
13268 KB |
Output is correct |
32 |
Correct |
2210 ms |
13424 KB |
Output is correct |
33 |
Correct |
1684 ms |
13384 KB |
Output is correct |
34 |
Correct |
1796 ms |
13424 KB |
Output is correct |
35 |
Correct |
1793 ms |
13560 KB |
Output is correct |
36 |
Correct |
1093 ms |
13172 KB |
Output is correct |
37 |
Correct |
1087 ms |
13052 KB |
Output is correct |
38 |
Correct |
1050 ms |
13256 KB |
Output is correct |
39 |
Correct |
536 ms |
11944 KB |
Output is correct |
40 |
Correct |
535 ms |
11772 KB |
Output is correct |
41 |
Correct |
518 ms |
11820 KB |
Output is correct |
42 |
Correct |
640 ms |
13584 KB |
Output is correct |
43 |
Correct |
631 ms |
13484 KB |
Output is correct |
44 |
Correct |
631 ms |
13588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
3 ms |
4992 KB |
Output is correct |
3 |
Correct |
83 ms |
5368 KB |
Output is correct |
4 |
Correct |
8 ms |
5120 KB |
Output is correct |
5 |
Correct |
28 ms |
5248 KB |
Output is correct |
6 |
Correct |
25 ms |
5248 KB |
Output is correct |
7 |
Correct |
29 ms |
5240 KB |
Output is correct |
8 |
Correct |
29 ms |
5240 KB |
Output is correct |
9 |
Correct |
37 ms |
5240 KB |
Output is correct |
10 |
Correct |
27 ms |
5244 KB |
Output is correct |
11 |
Correct |
26 ms |
5240 KB |
Output is correct |
12 |
Correct |
28 ms |
5248 KB |
Output is correct |
13 |
Correct |
37 ms |
5240 KB |
Output is correct |
14 |
Correct |
35 ms |
5248 KB |
Output is correct |
15 |
Correct |
36 ms |
5240 KB |
Output is correct |
16 |
Correct |
31 ms |
5240 KB |
Output is correct |
17 |
Correct |
30 ms |
5240 KB |
Output is correct |
18 |
Correct |
1828 ms |
10472 KB |
Output is correct |
19 |
Correct |
1798 ms |
10256 KB |
Output is correct |
20 |
Correct |
1623 ms |
10408 KB |
Output is correct |
21 |
Correct |
1521 ms |
10328 KB |
Output is correct |
22 |
Correct |
1605 ms |
10356 KB |
Output is correct |
23 |
Correct |
2904 ms |
9608 KB |
Output is correct |
24 |
Correct |
2922 ms |
12204 KB |
Output is correct |
25 |
Correct |
2535 ms |
12212 KB |
Output is correct |
26 |
Correct |
49 ms |
7928 KB |
Output is correct |
27 |
Correct |
2157 ms |
12008 KB |
Output is correct |
28 |
Correct |
1882 ms |
12096 KB |
Output is correct |
29 |
Correct |
1170 ms |
11232 KB |
Output is correct |
30 |
Correct |
1344 ms |
12812 KB |
Output is correct |
31 |
Correct |
1461 ms |
9432 KB |
Output is correct |
32 |
Correct |
1649 ms |
7428 KB |
Output is correct |
33 |
Correct |
2016 ms |
9628 KB |
Output is correct |
34 |
Correct |
1845 ms |
9388 KB |
Output is correct |
35 |
Correct |
49 ms |
6520 KB |
Output is correct |
36 |
Correct |
1712 ms |
9308 KB |
Output is correct |
37 |
Correct |
1761 ms |
9372 KB |
Output is correct |
38 |
Correct |
1059 ms |
9404 KB |
Output is correct |
39 |
Correct |
934 ms |
8424 KB |
Output is correct |
40 |
Correct |
627 ms |
8320 KB |
Output is correct |
41 |
Correct |
960 ms |
9572 KB |
Output is correct |
42 |
Correct |
800 ms |
9600 KB |
Output is correct |
43 |
Correct |
508 ms |
9388 KB |
Output is correct |
44 |
Correct |
50 ms |
6520 KB |
Output is correct |
45 |
Correct |
83 ms |
7360 KB |
Output is correct |
46 |
Correct |
59 ms |
7272 KB |
Output is correct |
47 |
Correct |
371 ms |
9432 KB |
Output is correct |
48 |
Correct |
506 ms |
9308 KB |
Output is correct |
49 |
Correct |
366 ms |
9564 KB |
Output is correct |
50 |
Correct |
283 ms |
8164 KB |
Output is correct |
51 |
Correct |
288 ms |
8036 KB |
Output is correct |
52 |
Correct |
286 ms |
8420 KB |
Output is correct |
53 |
Correct |
465 ms |
8600 KB |
Output is correct |
54 |
Correct |
453 ms |
8860 KB |
Output is correct |
55 |
Correct |
455 ms |
8872 KB |
Output is correct |
56 |
Correct |
362 ms |
9440 KB |
Output is correct |
57 |
Correct |
366 ms |
9436 KB |
Output is correct |
58 |
Correct |
561 ms |
9316 KB |
Output is correct |
59 |
Correct |
589 ms |
9444 KB |
Output is correct |
60 |
Correct |
552 ms |
9432 KB |
Output is correct |
61 |
Correct |
563 ms |
9312 KB |
Output is correct |
62 |
Correct |
517 ms |
9088 KB |
Output is correct |
63 |
Correct |
524 ms |
9440 KB |
Output is correct |
64 |
Correct |
537 ms |
9348 KB |
Output is correct |
65 |
Correct |
440 ms |
9076 KB |
Output is correct |
66 |
Correct |
1697 ms |
13428 KB |
Output is correct |
67 |
Correct |
2249 ms |
13572 KB |
Output is correct |
68 |
Correct |
1715 ms |
13292 KB |
Output is correct |
69 |
Correct |
1018 ms |
13064 KB |
Output is correct |
70 |
Correct |
2232 ms |
13420 KB |
Output is correct |
71 |
Correct |
2185 ms |
13268 KB |
Output is correct |
72 |
Correct |
2210 ms |
13424 KB |
Output is correct |
73 |
Correct |
1684 ms |
13384 KB |
Output is correct |
74 |
Correct |
1796 ms |
13424 KB |
Output is correct |
75 |
Correct |
1793 ms |
13560 KB |
Output is correct |
76 |
Correct |
1093 ms |
13172 KB |
Output is correct |
77 |
Correct |
1087 ms |
13052 KB |
Output is correct |
78 |
Correct |
1050 ms |
13256 KB |
Output is correct |
79 |
Correct |
536 ms |
11944 KB |
Output is correct |
80 |
Correct |
535 ms |
11772 KB |
Output is correct |
81 |
Correct |
518 ms |
11820 KB |
Output is correct |
82 |
Correct |
640 ms |
13584 KB |
Output is correct |
83 |
Correct |
631 ms |
13484 KB |
Output is correct |
84 |
Correct |
631 ms |
13588 KB |
Output is correct |
85 |
Correct |
1779 ms |
15796 KB |
Output is correct |
86 |
Correct |
183 ms |
9568 KB |
Output is correct |
87 |
Correct |
208 ms |
9696 KB |
Output is correct |
88 |
Correct |
1780 ms |
13748 KB |
Output is correct |
89 |
Correct |
1721 ms |
15792 KB |
Output is correct |
90 |
Correct |
1686 ms |
13432 KB |
Output is correct |
91 |
Correct |
1680 ms |
13392 KB |
Output is correct |
92 |
Correct |
1828 ms |
13356 KB |
Output is correct |
93 |
Correct |
2597 ms |
12432 KB |
Output is correct |
94 |
Correct |
1807 ms |
14736 KB |
Output is correct |
95 |
Correct |
1879 ms |
14872 KB |
Output is correct |
96 |
Correct |
2122 ms |
13912 KB |
Output is correct |
97 |
Correct |
797 ms |
12640 KB |
Output is correct |
98 |
Correct |
931 ms |
13920 KB |
Output is correct |
99 |
Correct |
1793 ms |
15664 KB |
Output is correct |
100 |
Correct |
1762 ms |
15824 KB |
Output is correct |
101 |
Correct |
1800 ms |
15860 KB |
Output is correct |
102 |
Correct |
1814 ms |
15916 KB |
Output is correct |
103 |
Correct |
2082 ms |
13628 KB |
Output is correct |
104 |
Correct |
2196 ms |
13652 KB |
Output is correct |
105 |
Correct |
1225 ms |
14352 KB |
Output is correct |
106 |
Correct |
836 ms |
14412 KB |
Output is correct |
107 |
Correct |
1085 ms |
12824 KB |
Output is correct |
108 |
Correct |
2005 ms |
14492 KB |
Output is correct |
109 |
Correct |
1978 ms |
12404 KB |
Output is correct |