#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
signed main() {
#ifndef DEBUG
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int N, M;
cin >> N >> M;
int A[M], B[M], D[M];
FOR(i, 0, M-1)
cin >> A[i] >> B[i] >> D[i], A[i]--, B[i]--;
constexpr int BSZ = 1050;
int Q;
cin >> Q;
int ans[Q];
memset(ans, -1, sizeof(ans));
REP(q, 0, Q-1, BSZ) {
vt<ari3> qrys, upds;
bool bad[M] = {};
int edge_cnt = M;
FOR(i, q, min(Q, q+BSZ)-1) {
int qt, a, b;
cin >> qt >> a >> b;
if (qt == 1)
upds.push_back({i, --a, b}), edge_cnt -= !bad[a], bad[a] = true;
else
qrys.push_back({b, --a, i});
}
sort(all(qrys), greater<ari3>());
reverse(all(upds));
const int upd_size = size(upds);
int edges[edge_cnt], edge_ptr = 0;
FOR(i, 0, M-1) {
if (bad[i])
upds.push_back({-1, i, D[i]});
else
edges[edge_ptr++] = i;
}
sort(edges, edges + edge_cnt, [&](const int &a, const int &b) {
return D[a] < D[b];
});
int uf[N], op_ptr = 0;
ari2 ops[N];
memset(uf, -1, sizeof(uf));
function<int(int)> find2 = [&](int i) {
return uf[i] < 0 ? i : uf[i] = find2(uf[i]);
};
auto find = [&](int i, bool b) {
if (!b)
return find2(i);
while (uf[i] >= 0)
i = uf[i];
return i;
};
auto unite = [&](int a, int b, bool c) {
if ((a = find(a, c)) == (b = find(b, c)))
return false;
if (uf[a] > uf[b])
swap(a, b);
if (c)
ops[op_ptr++] = {b, uf[b]};
uf[a] += uf[b];
uf[b] = a;
return true;
};
auto rollback = [&]() {
auto [b, v] = ops[--op_ptr];
uf[uf[b]] -= v;
uf[b] = v;
};
bool seen[M] = {};
for (auto [w, i, qi] : qrys) {
while (edge_ptr && D[edges[edge_ptr-1]] >= w) {
edge_ptr--;
unite(A[edges[edge_ptr]], B[edges[edge_ptr]], 0);
}
int cnt = 0;
for (auto [ui, b, k] : upds) {
if (ui > qi)
continue;
if (!seen[b] && k >= w)
cnt += unite(A[b], B[b], 1);
seen[b] = true;
}
ans[qi] = -uf[find(i, 1)];
while (cnt--)
rollback();
FOR(j, upd_size, size(upds)-1)
seen[upds[j][1]] = false;
}
FOR(i, 0, upd_size-1) { // cOnStAnT oPtImIsAtIoN
auto [ui, b, k] = upds[i];
if (seen[b])
continue;
D[b] = k;
seen[b] = true;
}
}
FOR(i, 0, Q-1)
if (~ans[i])
cout << ans[i] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
16 ms |
724 KB |
Output is correct |
4 |
Correct |
3 ms |
604 KB |
Output is correct |
5 |
Correct |
12 ms |
604 KB |
Output is correct |
6 |
Correct |
11 ms |
692 KB |
Output is correct |
7 |
Correct |
10 ms |
856 KB |
Output is correct |
8 |
Correct |
10 ms |
604 KB |
Output is correct |
9 |
Correct |
12 ms |
604 KB |
Output is correct |
10 |
Correct |
11 ms |
600 KB |
Output is correct |
11 |
Correct |
11 ms |
604 KB |
Output is correct |
12 |
Correct |
15 ms |
860 KB |
Output is correct |
13 |
Correct |
15 ms |
680 KB |
Output is correct |
14 |
Correct |
14 ms |
604 KB |
Output is correct |
15 |
Correct |
13 ms |
600 KB |
Output is correct |
16 |
Correct |
11 ms |
468 KB |
Output is correct |
17 |
Correct |
11 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
828 ms |
5024 KB |
Output is correct |
2 |
Correct |
853 ms |
5160 KB |
Output is correct |
3 |
Correct |
850 ms |
5156 KB |
Output is correct |
4 |
Correct |
890 ms |
5140 KB |
Output is correct |
5 |
Correct |
887 ms |
5180 KB |
Output is correct |
6 |
Correct |
1304 ms |
5544 KB |
Output is correct |
7 |
Correct |
1297 ms |
5424 KB |
Output is correct |
8 |
Correct |
1287 ms |
5280 KB |
Output is correct |
9 |
Correct |
29 ms |
2384 KB |
Output is correct |
10 |
Correct |
672 ms |
4004 KB |
Output is correct |
11 |
Correct |
613 ms |
4008 KB |
Output is correct |
12 |
Correct |
701 ms |
5112 KB |
Output is correct |
13 |
Correct |
802 ms |
4880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
596 ms |
4272 KB |
Output is correct |
2 |
Correct |
388 ms |
2672 KB |
Output is correct |
3 |
Correct |
659 ms |
3964 KB |
Output is correct |
4 |
Correct |
600 ms |
4268 KB |
Output is correct |
5 |
Correct |
26 ms |
2268 KB |
Output is correct |
6 |
Correct |
625 ms |
4436 KB |
Output is correct |
7 |
Correct |
559 ms |
4148 KB |
Output is correct |
8 |
Correct |
508 ms |
4156 KB |
Output is correct |
9 |
Correct |
423 ms |
4332 KB |
Output is correct |
10 |
Correct |
404 ms |
4360 KB |
Output is correct |
11 |
Correct |
444 ms |
3992 KB |
Output is correct |
12 |
Correct |
408 ms |
3924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1136 ms |
7300 KB |
Output is correct |
2 |
Correct |
26 ms |
2388 KB |
Output is correct |
3 |
Correct |
123 ms |
4120 KB |
Output is correct |
4 |
Correct |
48 ms |
4032 KB |
Output is correct |
5 |
Correct |
538 ms |
5812 KB |
Output is correct |
6 |
Correct |
1115 ms |
7420 KB |
Output is correct |
7 |
Correct |
545 ms |
5768 KB |
Output is correct |
8 |
Correct |
545 ms |
5228 KB |
Output is correct |
9 |
Correct |
538 ms |
5456 KB |
Output is correct |
10 |
Correct |
543 ms |
5004 KB |
Output is correct |
11 |
Correct |
909 ms |
6088 KB |
Output is correct |
12 |
Correct |
870 ms |
6336 KB |
Output is correct |
13 |
Correct |
907 ms |
6340 KB |
Output is correct |
14 |
Correct |
483 ms |
5972 KB |
Output is correct |
15 |
Correct |
500 ms |
6012 KB |
Output is correct |
16 |
Correct |
1177 ms |
7428 KB |
Output is correct |
17 |
Correct |
1187 ms |
7152 KB |
Output is correct |
18 |
Correct |
1171 ms |
7284 KB |
Output is correct |
19 |
Correct |
1177 ms |
7284 KB |
Output is correct |
20 |
Correct |
1039 ms |
6736 KB |
Output is correct |
21 |
Correct |
1018 ms |
6752 KB |
Output is correct |
22 |
Correct |
1136 ms |
7224 KB |
Output is correct |
23 |
Correct |
670 ms |
5472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
828 ms |
5024 KB |
Output is correct |
2 |
Correct |
853 ms |
5160 KB |
Output is correct |
3 |
Correct |
850 ms |
5156 KB |
Output is correct |
4 |
Correct |
890 ms |
5140 KB |
Output is correct |
5 |
Correct |
887 ms |
5180 KB |
Output is correct |
6 |
Correct |
1304 ms |
5544 KB |
Output is correct |
7 |
Correct |
1297 ms |
5424 KB |
Output is correct |
8 |
Correct |
1287 ms |
5280 KB |
Output is correct |
9 |
Correct |
29 ms |
2384 KB |
Output is correct |
10 |
Correct |
672 ms |
4004 KB |
Output is correct |
11 |
Correct |
613 ms |
4008 KB |
Output is correct |
12 |
Correct |
701 ms |
5112 KB |
Output is correct |
13 |
Correct |
802 ms |
4880 KB |
Output is correct |
14 |
Correct |
596 ms |
4272 KB |
Output is correct |
15 |
Correct |
388 ms |
2672 KB |
Output is correct |
16 |
Correct |
659 ms |
3964 KB |
Output is correct |
17 |
Correct |
600 ms |
4268 KB |
Output is correct |
18 |
Correct |
26 ms |
2268 KB |
Output is correct |
19 |
Correct |
625 ms |
4436 KB |
Output is correct |
20 |
Correct |
559 ms |
4148 KB |
Output is correct |
21 |
Correct |
508 ms |
4156 KB |
Output is correct |
22 |
Correct |
423 ms |
4332 KB |
Output is correct |
23 |
Correct |
404 ms |
4360 KB |
Output is correct |
24 |
Correct |
444 ms |
3992 KB |
Output is correct |
25 |
Correct |
408 ms |
3924 KB |
Output is correct |
26 |
Correct |
783 ms |
5204 KB |
Output is correct |
27 |
Correct |
953 ms |
5096 KB |
Output is correct |
28 |
Correct |
867 ms |
5160 KB |
Output is correct |
29 |
Correct |
702 ms |
5200 KB |
Output is correct |
30 |
Correct |
1034 ms |
4984 KB |
Output is correct |
31 |
Correct |
1056 ms |
5172 KB |
Output is correct |
32 |
Correct |
1054 ms |
5204 KB |
Output is correct |
33 |
Correct |
866 ms |
5152 KB |
Output is correct |
34 |
Correct |
867 ms |
5148 KB |
Output is correct |
35 |
Correct |
890 ms |
5140 KB |
Output is correct |
36 |
Correct |
718 ms |
5088 KB |
Output is correct |
37 |
Correct |
720 ms |
5288 KB |
Output is correct |
38 |
Correct |
733 ms |
5160 KB |
Output is correct |
39 |
Correct |
603 ms |
5204 KB |
Output is correct |
40 |
Correct |
597 ms |
5116 KB |
Output is correct |
41 |
Correct |
593 ms |
5244 KB |
Output is correct |
42 |
Correct |
611 ms |
4880 KB |
Output is correct |
43 |
Correct |
605 ms |
5008 KB |
Output is correct |
44 |
Correct |
644 ms |
5040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
16 ms |
724 KB |
Output is correct |
4 |
Correct |
3 ms |
604 KB |
Output is correct |
5 |
Correct |
12 ms |
604 KB |
Output is correct |
6 |
Correct |
11 ms |
692 KB |
Output is correct |
7 |
Correct |
10 ms |
856 KB |
Output is correct |
8 |
Correct |
10 ms |
604 KB |
Output is correct |
9 |
Correct |
12 ms |
604 KB |
Output is correct |
10 |
Correct |
11 ms |
600 KB |
Output is correct |
11 |
Correct |
11 ms |
604 KB |
Output is correct |
12 |
Correct |
15 ms |
860 KB |
Output is correct |
13 |
Correct |
15 ms |
680 KB |
Output is correct |
14 |
Correct |
14 ms |
604 KB |
Output is correct |
15 |
Correct |
13 ms |
600 KB |
Output is correct |
16 |
Correct |
11 ms |
468 KB |
Output is correct |
17 |
Correct |
11 ms |
604 KB |
Output is correct |
18 |
Correct |
828 ms |
5024 KB |
Output is correct |
19 |
Correct |
853 ms |
5160 KB |
Output is correct |
20 |
Correct |
850 ms |
5156 KB |
Output is correct |
21 |
Correct |
890 ms |
5140 KB |
Output is correct |
22 |
Correct |
887 ms |
5180 KB |
Output is correct |
23 |
Correct |
1304 ms |
5544 KB |
Output is correct |
24 |
Correct |
1297 ms |
5424 KB |
Output is correct |
25 |
Correct |
1287 ms |
5280 KB |
Output is correct |
26 |
Correct |
29 ms |
2384 KB |
Output is correct |
27 |
Correct |
672 ms |
4004 KB |
Output is correct |
28 |
Correct |
613 ms |
4008 KB |
Output is correct |
29 |
Correct |
701 ms |
5112 KB |
Output is correct |
30 |
Correct |
802 ms |
4880 KB |
Output is correct |
31 |
Correct |
596 ms |
4272 KB |
Output is correct |
32 |
Correct |
388 ms |
2672 KB |
Output is correct |
33 |
Correct |
659 ms |
3964 KB |
Output is correct |
34 |
Correct |
600 ms |
4268 KB |
Output is correct |
35 |
Correct |
26 ms |
2268 KB |
Output is correct |
36 |
Correct |
625 ms |
4436 KB |
Output is correct |
37 |
Correct |
559 ms |
4148 KB |
Output is correct |
38 |
Correct |
508 ms |
4156 KB |
Output is correct |
39 |
Correct |
423 ms |
4332 KB |
Output is correct |
40 |
Correct |
404 ms |
4360 KB |
Output is correct |
41 |
Correct |
444 ms |
3992 KB |
Output is correct |
42 |
Correct |
408 ms |
3924 KB |
Output is correct |
43 |
Correct |
1136 ms |
7300 KB |
Output is correct |
44 |
Correct |
26 ms |
2388 KB |
Output is correct |
45 |
Correct |
123 ms |
4120 KB |
Output is correct |
46 |
Correct |
48 ms |
4032 KB |
Output is correct |
47 |
Correct |
538 ms |
5812 KB |
Output is correct |
48 |
Correct |
1115 ms |
7420 KB |
Output is correct |
49 |
Correct |
545 ms |
5768 KB |
Output is correct |
50 |
Correct |
545 ms |
5228 KB |
Output is correct |
51 |
Correct |
538 ms |
5456 KB |
Output is correct |
52 |
Correct |
543 ms |
5004 KB |
Output is correct |
53 |
Correct |
909 ms |
6088 KB |
Output is correct |
54 |
Correct |
870 ms |
6336 KB |
Output is correct |
55 |
Correct |
907 ms |
6340 KB |
Output is correct |
56 |
Correct |
483 ms |
5972 KB |
Output is correct |
57 |
Correct |
500 ms |
6012 KB |
Output is correct |
58 |
Correct |
1177 ms |
7428 KB |
Output is correct |
59 |
Correct |
1187 ms |
7152 KB |
Output is correct |
60 |
Correct |
1171 ms |
7284 KB |
Output is correct |
61 |
Correct |
1177 ms |
7284 KB |
Output is correct |
62 |
Correct |
1039 ms |
6736 KB |
Output is correct |
63 |
Correct |
1018 ms |
6752 KB |
Output is correct |
64 |
Correct |
1136 ms |
7224 KB |
Output is correct |
65 |
Correct |
670 ms |
5472 KB |
Output is correct |
66 |
Correct |
783 ms |
5204 KB |
Output is correct |
67 |
Correct |
953 ms |
5096 KB |
Output is correct |
68 |
Correct |
867 ms |
5160 KB |
Output is correct |
69 |
Correct |
702 ms |
5200 KB |
Output is correct |
70 |
Correct |
1034 ms |
4984 KB |
Output is correct |
71 |
Correct |
1056 ms |
5172 KB |
Output is correct |
72 |
Correct |
1054 ms |
5204 KB |
Output is correct |
73 |
Correct |
866 ms |
5152 KB |
Output is correct |
74 |
Correct |
867 ms |
5148 KB |
Output is correct |
75 |
Correct |
890 ms |
5140 KB |
Output is correct |
76 |
Correct |
718 ms |
5088 KB |
Output is correct |
77 |
Correct |
720 ms |
5288 KB |
Output is correct |
78 |
Correct |
733 ms |
5160 KB |
Output is correct |
79 |
Correct |
603 ms |
5204 KB |
Output is correct |
80 |
Correct |
597 ms |
5116 KB |
Output is correct |
81 |
Correct |
593 ms |
5244 KB |
Output is correct |
82 |
Correct |
611 ms |
4880 KB |
Output is correct |
83 |
Correct |
605 ms |
5008 KB |
Output is correct |
84 |
Correct |
644 ms |
5040 KB |
Output is correct |
85 |
Correct |
1372 ms |
7072 KB |
Output is correct |
86 |
Correct |
135 ms |
4180 KB |
Output is correct |
87 |
Correct |
68 ms |
4436 KB |
Output is correct |
88 |
Correct |
716 ms |
5716 KB |
Output is correct |
89 |
Correct |
1379 ms |
7068 KB |
Output is correct |
90 |
Correct |
733 ms |
5888 KB |
Output is correct |
91 |
Correct |
907 ms |
5276 KB |
Output is correct |
92 |
Correct |
913 ms |
5024 KB |
Output is correct |
93 |
Correct |
1251 ms |
4948 KB |
Output is correct |
94 |
Correct |
1268 ms |
5984 KB |
Output is correct |
95 |
Correct |
1217 ms |
6124 KB |
Output is correct |
96 |
Correct |
1276 ms |
6224 KB |
Output is correct |
97 |
Correct |
594 ms |
5864 KB |
Output is correct |
98 |
Correct |
629 ms |
5512 KB |
Output is correct |
99 |
Correct |
1457 ms |
7176 KB |
Output is correct |
100 |
Correct |
1444 ms |
7024 KB |
Output is correct |
101 |
Correct |
1472 ms |
7256 KB |
Output is correct |
102 |
Correct |
1470 ms |
7248 KB |
Output is correct |
103 |
Correct |
1321 ms |
6608 KB |
Output is correct |
104 |
Correct |
1336 ms |
6640 KB |
Output is correct |
105 |
Correct |
1161 ms |
6380 KB |
Output is correct |
106 |
Correct |
979 ms |
5832 KB |
Output is correct |
107 |
Correct |
1095 ms |
6468 KB |
Output is correct |
108 |
Correct |
1389 ms |
6992 KB |
Output is correct |
109 |
Correct |
899 ms |
5200 KB |
Output is correct |