#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize(3)
#pragma GCC optimize("O3")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
struct dsu_save {
int v, rnkv, u, rnku;
dsu_save() {}
dsu_save(int _v, int _rnkv, int _u, int _rnku)
: v(_v), rnkv(_rnkv), u(_u), rnku(_rnku) {}
};
struct dsu_with_rollbacks {
vector<int> p, rnk;
int comps;
stack<dsu_save> op;
dsu_with_rollbacks() {}
dsu_with_rollbacks(int n) {
p.resize(n);
rnk.resize(n);
for (int i = 0; i < n; i++) {
p[i] = i;
rnk[i] = 1;
}
comps = n;
}
int find_set(int v) {
return (v == p[v]) ? v : find_set(p[v]);
}
bool unite(int v, int u) {
v = find_set(v);
u = find_set(u);
if (v == u)
return false;
comps--;
if (rnk[v] > rnk[u])
swap(v, u);
op.push(dsu_save(v, rnk[v], u, rnk[u]));
p[v] = u;
rnk[u] += rnk[v];
return true;
}
void rollback() {
if (op.empty())
return;
dsu_save x = op.top();
op.pop();
comps++;
p[x.v] = x.v;
rnk[x.v] = x.rnkv;
p[x.u] = x.u;
rnk[x.u] = x.rnku;
}
};
struct edge {
int from, to;
int weight;
};
bool operator>(edge a, edge b) {
return a.weight > b.weight;
}
const int BLOCK = 1050;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N, M;
cin >> N >> M;
vector<edge> edges(M);
for (auto &[from, to, weight] : edges) {
cin >> from >> to >> weight;
from--, to--;
}
int Q;
cin >> Q;
vector<int> answer(Q, -1);
vector<tuple<int, int, int>> changes, queries;
vector<bool> is_changed(M), used(M);
for (int i = 0; i < Q; i++) {
int T;
cin >> T;
if (T == 1) {
int B, R;
cin >> B >> R;
B--;
is_changed[B] = true;
changes.push_back({i, B, R});
} else {
int S, W;
cin >> S >> W;
S--;
queries.push_back({i, S, W});
}
if ((Q - i - 1) % BLOCK == 0) {
vector<pair<edge, int>> sorted_edges(M);
for (int i = 0; i < M; i++) {
sorted_edges[i] = {edges[i], i};
}
sort(sorted_edges.begin(), sorted_edges.end(),
[](pair<edge, int>& a, pair<edge, int>& b) {
return a.first > b.first;
});
sort(queries.begin(), queries.end(),
[](tuple<int, int, int> a, tuple<int, int, int> b) {
return get<2>(a) > get<2>(b);
});
int ptr = 0;
dsu_with_rollbacks sets(N);
for (auto [j, S, W] : queries) {
while (ptr < M && sorted_edges[ptr].first.weight >= W) {
if (!is_changed[sorted_edges[ptr].second]) {
sets.unite(sorted_edges[ptr].first.from, sorted_edges[ptr].first.to);
}
ptr++;
}
int x = (int)changes.size();
for (int k = 0; k < (int)changes.size(); k++) {
if (get<0>(changes[k]) > j) {
x = k;
break;
}
}
int rollbacks = 0;
for (int k = x - 1; k >= 0; k--) {
if (!used[get<1>(changes[k])] && get<2>(changes[k]) >= W) {
auto [from, to, weight] = edges[get<1>(changes[k])];
rollbacks += sets.unite(from, to);
}
used[get<1>(changes[k])] = true;
}
for (int k = (int)changes.size() - 1; k >= x; k--) {
auto [y, B, R] = changes[k];
if (!used[B] && edges[B].weight >= W) {
used[B] = true;
rollbacks += sets.unite(edges[B].from, edges[B].to);
}
}
answer[j] = sets.rnk[sets.find_set(S)];
for (int k = (int)changes.size() - 1; k >= 0; k--) {
used[get<1>(changes[k])] = false;
}
for (int k = 0; k < rollbacks; k++) {
sets.rollback();
}
}
for (auto [j, B, R] : changes) {
is_changed[B] = false;
edges[B].weight = R;
}
vector<tuple<int, int, int>>().swap(changes);
vector<tuple<int, int, int>>().swap(queries);
}
}
for (int i = 0; i < Q; i++) {
if (answer[i] != -1) {
cout << answer[i] << "\n";
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
18 ms |
740 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
5 |
Correct |
18 ms |
676 KB |
Output is correct |
6 |
Correct |
16 ms |
696 KB |
Output is correct |
7 |
Correct |
17 ms |
604 KB |
Output is correct |
8 |
Correct |
18 ms |
688 KB |
Output is correct |
9 |
Correct |
16 ms |
604 KB |
Output is correct |
10 |
Correct |
18 ms |
680 KB |
Output is correct |
11 |
Correct |
20 ms |
860 KB |
Output is correct |
12 |
Correct |
19 ms |
860 KB |
Output is correct |
13 |
Correct |
22 ms |
692 KB |
Output is correct |
14 |
Correct |
21 ms |
656 KB |
Output is correct |
15 |
Correct |
20 ms |
856 KB |
Output is correct |
16 |
Correct |
17 ms |
608 KB |
Output is correct |
17 |
Correct |
17 ms |
856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
842 ms |
6404 KB |
Output is correct |
2 |
Correct |
861 ms |
6324 KB |
Output is correct |
3 |
Correct |
857 ms |
6280 KB |
Output is correct |
4 |
Correct |
947 ms |
6400 KB |
Output is correct |
5 |
Correct |
973 ms |
6160 KB |
Output is correct |
6 |
Correct |
1490 ms |
6276 KB |
Output is correct |
7 |
Correct |
1493 ms |
6528 KB |
Output is correct |
8 |
Correct |
1476 ms |
6156 KB |
Output is correct |
9 |
Correct |
26 ms |
2388 KB |
Output is correct |
10 |
Correct |
745 ms |
5088 KB |
Output is correct |
11 |
Correct |
712 ms |
5048 KB |
Output is correct |
12 |
Correct |
720 ms |
6396 KB |
Output is correct |
13 |
Correct |
845 ms |
6136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
684 ms |
4876 KB |
Output is correct |
2 |
Correct |
536 ms |
2948 KB |
Output is correct |
3 |
Correct |
779 ms |
4824 KB |
Output is correct |
4 |
Correct |
660 ms |
5124 KB |
Output is correct |
5 |
Correct |
26 ms |
2384 KB |
Output is correct |
6 |
Correct |
757 ms |
4936 KB |
Output is correct |
7 |
Correct |
624 ms |
5036 KB |
Output is correct |
8 |
Correct |
558 ms |
5088 KB |
Output is correct |
9 |
Correct |
441 ms |
5136 KB |
Output is correct |
10 |
Correct |
399 ms |
4984 KB |
Output is correct |
11 |
Correct |
485 ms |
4856 KB |
Output is correct |
12 |
Correct |
420 ms |
4684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
934 ms |
8924 KB |
Output is correct |
2 |
Correct |
26 ms |
2348 KB |
Output is correct |
3 |
Correct |
106 ms |
5140 KB |
Output is correct |
4 |
Correct |
56 ms |
5212 KB |
Output is correct |
5 |
Correct |
532 ms |
7452 KB |
Output is correct |
6 |
Correct |
902 ms |
9040 KB |
Output is correct |
7 |
Correct |
524 ms |
7376 KB |
Output is correct |
8 |
Correct |
494 ms |
6140 KB |
Output is correct |
9 |
Correct |
494 ms |
6492 KB |
Output is correct |
10 |
Correct |
493 ms |
6000 KB |
Output is correct |
11 |
Correct |
750 ms |
7328 KB |
Output is correct |
12 |
Correct |
744 ms |
7468 KB |
Output is correct |
13 |
Correct |
775 ms |
7224 KB |
Output is correct |
14 |
Correct |
500 ms |
7764 KB |
Output is correct |
15 |
Correct |
508 ms |
7504 KB |
Output is correct |
16 |
Correct |
930 ms |
8976 KB |
Output is correct |
17 |
Correct |
942 ms |
8980 KB |
Output is correct |
18 |
Correct |
929 ms |
9096 KB |
Output is correct |
19 |
Correct |
928 ms |
8976 KB |
Output is correct |
20 |
Correct |
858 ms |
7736 KB |
Output is correct |
21 |
Correct |
851 ms |
7532 KB |
Output is correct |
22 |
Correct |
906 ms |
8788 KB |
Output is correct |
23 |
Correct |
556 ms |
6844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
842 ms |
6404 KB |
Output is correct |
2 |
Correct |
861 ms |
6324 KB |
Output is correct |
3 |
Correct |
857 ms |
6280 KB |
Output is correct |
4 |
Correct |
947 ms |
6400 KB |
Output is correct |
5 |
Correct |
973 ms |
6160 KB |
Output is correct |
6 |
Correct |
1490 ms |
6276 KB |
Output is correct |
7 |
Correct |
1493 ms |
6528 KB |
Output is correct |
8 |
Correct |
1476 ms |
6156 KB |
Output is correct |
9 |
Correct |
26 ms |
2388 KB |
Output is correct |
10 |
Correct |
745 ms |
5088 KB |
Output is correct |
11 |
Correct |
712 ms |
5048 KB |
Output is correct |
12 |
Correct |
720 ms |
6396 KB |
Output is correct |
13 |
Correct |
845 ms |
6136 KB |
Output is correct |
14 |
Correct |
684 ms |
4876 KB |
Output is correct |
15 |
Correct |
536 ms |
2948 KB |
Output is correct |
16 |
Correct |
779 ms |
4824 KB |
Output is correct |
17 |
Correct |
660 ms |
5124 KB |
Output is correct |
18 |
Correct |
26 ms |
2384 KB |
Output is correct |
19 |
Correct |
757 ms |
4936 KB |
Output is correct |
20 |
Correct |
624 ms |
5036 KB |
Output is correct |
21 |
Correct |
558 ms |
5088 KB |
Output is correct |
22 |
Correct |
441 ms |
5136 KB |
Output is correct |
23 |
Correct |
399 ms |
4984 KB |
Output is correct |
24 |
Correct |
485 ms |
4856 KB |
Output is correct |
25 |
Correct |
420 ms |
4684 KB |
Output is correct |
26 |
Correct |
870 ms |
6148 KB |
Output is correct |
27 |
Correct |
1008 ms |
6072 KB |
Output is correct |
28 |
Correct |
868 ms |
6392 KB |
Output is correct |
29 |
Correct |
647 ms |
6556 KB |
Output is correct |
30 |
Correct |
1038 ms |
6156 KB |
Output is correct |
31 |
Correct |
1051 ms |
6024 KB |
Output is correct |
32 |
Correct |
1047 ms |
6068 KB |
Output is correct |
33 |
Correct |
869 ms |
6328 KB |
Output is correct |
34 |
Correct |
876 ms |
6328 KB |
Output is correct |
35 |
Correct |
879 ms |
6320 KB |
Output is correct |
36 |
Correct |
674 ms |
6204 KB |
Output is correct |
37 |
Correct |
678 ms |
6324 KB |
Output is correct |
38 |
Correct |
658 ms |
6288 KB |
Output is correct |
39 |
Correct |
526 ms |
6328 KB |
Output is correct |
40 |
Correct |
526 ms |
6392 KB |
Output is correct |
41 |
Correct |
534 ms |
6268 KB |
Output is correct |
42 |
Correct |
523 ms |
6136 KB |
Output is correct |
43 |
Correct |
535 ms |
6132 KB |
Output is correct |
44 |
Correct |
533 ms |
6128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
18 ms |
740 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
5 |
Correct |
18 ms |
676 KB |
Output is correct |
6 |
Correct |
16 ms |
696 KB |
Output is correct |
7 |
Correct |
17 ms |
604 KB |
Output is correct |
8 |
Correct |
18 ms |
688 KB |
Output is correct |
9 |
Correct |
16 ms |
604 KB |
Output is correct |
10 |
Correct |
18 ms |
680 KB |
Output is correct |
11 |
Correct |
20 ms |
860 KB |
Output is correct |
12 |
Correct |
19 ms |
860 KB |
Output is correct |
13 |
Correct |
22 ms |
692 KB |
Output is correct |
14 |
Correct |
21 ms |
656 KB |
Output is correct |
15 |
Correct |
20 ms |
856 KB |
Output is correct |
16 |
Correct |
17 ms |
608 KB |
Output is correct |
17 |
Correct |
17 ms |
856 KB |
Output is correct |
18 |
Correct |
842 ms |
6404 KB |
Output is correct |
19 |
Correct |
861 ms |
6324 KB |
Output is correct |
20 |
Correct |
857 ms |
6280 KB |
Output is correct |
21 |
Correct |
947 ms |
6400 KB |
Output is correct |
22 |
Correct |
973 ms |
6160 KB |
Output is correct |
23 |
Correct |
1490 ms |
6276 KB |
Output is correct |
24 |
Correct |
1493 ms |
6528 KB |
Output is correct |
25 |
Correct |
1476 ms |
6156 KB |
Output is correct |
26 |
Correct |
26 ms |
2388 KB |
Output is correct |
27 |
Correct |
745 ms |
5088 KB |
Output is correct |
28 |
Correct |
712 ms |
5048 KB |
Output is correct |
29 |
Correct |
720 ms |
6396 KB |
Output is correct |
30 |
Correct |
845 ms |
6136 KB |
Output is correct |
31 |
Correct |
684 ms |
4876 KB |
Output is correct |
32 |
Correct |
536 ms |
2948 KB |
Output is correct |
33 |
Correct |
779 ms |
4824 KB |
Output is correct |
34 |
Correct |
660 ms |
5124 KB |
Output is correct |
35 |
Correct |
26 ms |
2384 KB |
Output is correct |
36 |
Correct |
757 ms |
4936 KB |
Output is correct |
37 |
Correct |
624 ms |
5036 KB |
Output is correct |
38 |
Correct |
558 ms |
5088 KB |
Output is correct |
39 |
Correct |
441 ms |
5136 KB |
Output is correct |
40 |
Correct |
399 ms |
4984 KB |
Output is correct |
41 |
Correct |
485 ms |
4856 KB |
Output is correct |
42 |
Correct |
420 ms |
4684 KB |
Output is correct |
43 |
Correct |
934 ms |
8924 KB |
Output is correct |
44 |
Correct |
26 ms |
2348 KB |
Output is correct |
45 |
Correct |
106 ms |
5140 KB |
Output is correct |
46 |
Correct |
56 ms |
5212 KB |
Output is correct |
47 |
Correct |
532 ms |
7452 KB |
Output is correct |
48 |
Correct |
902 ms |
9040 KB |
Output is correct |
49 |
Correct |
524 ms |
7376 KB |
Output is correct |
50 |
Correct |
494 ms |
6140 KB |
Output is correct |
51 |
Correct |
494 ms |
6492 KB |
Output is correct |
52 |
Correct |
493 ms |
6000 KB |
Output is correct |
53 |
Correct |
750 ms |
7328 KB |
Output is correct |
54 |
Correct |
744 ms |
7468 KB |
Output is correct |
55 |
Correct |
775 ms |
7224 KB |
Output is correct |
56 |
Correct |
500 ms |
7764 KB |
Output is correct |
57 |
Correct |
508 ms |
7504 KB |
Output is correct |
58 |
Correct |
930 ms |
8976 KB |
Output is correct |
59 |
Correct |
942 ms |
8980 KB |
Output is correct |
60 |
Correct |
929 ms |
9096 KB |
Output is correct |
61 |
Correct |
928 ms |
8976 KB |
Output is correct |
62 |
Correct |
858 ms |
7736 KB |
Output is correct |
63 |
Correct |
851 ms |
7532 KB |
Output is correct |
64 |
Correct |
906 ms |
8788 KB |
Output is correct |
65 |
Correct |
556 ms |
6844 KB |
Output is correct |
66 |
Correct |
870 ms |
6148 KB |
Output is correct |
67 |
Correct |
1008 ms |
6072 KB |
Output is correct |
68 |
Correct |
868 ms |
6392 KB |
Output is correct |
69 |
Correct |
647 ms |
6556 KB |
Output is correct |
70 |
Correct |
1038 ms |
6156 KB |
Output is correct |
71 |
Correct |
1051 ms |
6024 KB |
Output is correct |
72 |
Correct |
1047 ms |
6068 KB |
Output is correct |
73 |
Correct |
869 ms |
6328 KB |
Output is correct |
74 |
Correct |
876 ms |
6328 KB |
Output is correct |
75 |
Correct |
879 ms |
6320 KB |
Output is correct |
76 |
Correct |
674 ms |
6204 KB |
Output is correct |
77 |
Correct |
678 ms |
6324 KB |
Output is correct |
78 |
Correct |
658 ms |
6288 KB |
Output is correct |
79 |
Correct |
526 ms |
6328 KB |
Output is correct |
80 |
Correct |
526 ms |
6392 KB |
Output is correct |
81 |
Correct |
534 ms |
6268 KB |
Output is correct |
82 |
Correct |
523 ms |
6136 KB |
Output is correct |
83 |
Correct |
535 ms |
6132 KB |
Output is correct |
84 |
Correct |
533 ms |
6128 KB |
Output is correct |
85 |
Correct |
1223 ms |
8672 KB |
Output is correct |
86 |
Correct |
119 ms |
5172 KB |
Output is correct |
87 |
Correct |
78 ms |
5560 KB |
Output is correct |
88 |
Correct |
764 ms |
7212 KB |
Output is correct |
89 |
Correct |
1184 ms |
8876 KB |
Output is correct |
90 |
Correct |
770 ms |
7324 KB |
Output is correct |
91 |
Correct |
926 ms |
6276 KB |
Output is correct |
92 |
Correct |
917 ms |
6404 KB |
Output is correct |
93 |
Correct |
1367 ms |
6204 KB |
Output is correct |
94 |
Correct |
1046 ms |
7336 KB |
Output is correct |
95 |
Correct |
1058 ms |
7612 KB |
Output is correct |
96 |
Correct |
1141 ms |
7300 KB |
Output is correct |
97 |
Correct |
614 ms |
7360 KB |
Output is correct |
98 |
Correct |
632 ms |
7308 KB |
Output is correct |
99 |
Correct |
1212 ms |
8848 KB |
Output is correct |
100 |
Correct |
1204 ms |
8524 KB |
Output is correct |
101 |
Correct |
1239 ms |
8796 KB |
Output is correct |
102 |
Correct |
1230 ms |
8976 KB |
Output is correct |
103 |
Correct |
1248 ms |
7680 KB |
Output is correct |
104 |
Correct |
1229 ms |
7656 KB |
Output is correct |
105 |
Correct |
1024 ms |
7852 KB |
Output is correct |
106 |
Correct |
802 ms |
7340 KB |
Output is correct |
107 |
Correct |
980 ms |
7912 KB |
Output is correct |
108 |
Correct |
1175 ms |
8516 KB |
Output is correct |
109 |
Correct |
805 ms |
6344 KB |
Output is correct |