// Comment(Offline, MST, Sqrt)
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;
using ti = tuple<int, int, int>;
using qi = tuple<int, int, int, int>;
const int MAX_N = 5e4 + 100;
const int MAX_Q = 1e5 + 100;
const int ROOT = 750;
struct UF {
int UNF[MAX_N], S[MAX_N], R[MAX_N];
stack<qi> stk;
void init(int n) {
for(int i=0; i<n; i++) UNF[i] = i, S[i] = 1, R[i] = 0;
while(!stk.empty()) stk.pop();
}
int find(int v) {
if(UNF[v] == v) return v;
return find(UNF[v]);
}
void merge(int a, int b, bool use) {
a = find(a), b = find(b);
if(a == b) return;
if(R[a] > R[b]) swap(a, b);
if(use) stk.emplace(1, a, b, UNF[a]);
UNF[a] = b;
S[b] = S[a] + S[b];
if(R[a] == R[b]) {
R[b] = R[b] + 1;
if(use) stk.emplace(2, -1, b, -1);
}
}
void rollback() {
while(!stk.empty()) {
int t, a, b, v; tie(t, a, b, v) = stk.top(); stk.pop();
if(t == 1) {
UNF[a] = v;
S[b] = S[b] - S[a];
}else{
R[b] = R[b] - 1;
}
}
}
};
int N, M, Q;
vector<qi> Ls;
vector<ti> Qs;
int Ans[MAX_Q];
int main() {
cin >> N >> M;
for(int i=0; i<M; i++) {
int x, y, c; scanf("%d%d%d", &x, &y, &c);
x--; y--;
Ls.emplace_back(c, x, y, i);
}
cin >> Q;
for(int i=0; i<Q; i++) {
int t, x, y; scanf("%d%d%d", &t, &x, &y);
x = x-1;
Qs.emplace_back(t, x, y);
}
UF uf;
vector<qi> ls;
vector<int> rev(M, 0);
vector<int> change(M, -1);
for(int r=0; r<(Q+ROOT-1)/ROOT; r++) {
int ql = r*ROOT, qr = min((r+1)*ROOT, Q);
ls = Ls;
sort(ALL(ls), [](qi &a, qi &b) { return get<0>(a) > get<0>(b);});
for(int i=0; i<M; i++) rev[get<3>(ls[i])] = i;
vector<int> edIx;
for(int i=0; i<M; i++) change[i] = -1;
for(int q=ql; q<qr; q++) {
int t, x, y; tie(t, x, y) = Qs[q];
if(t == 1) {
if(change[x] == -1) {
change[x] = SZ(edIx);
edIx.push_back(x);
}
}
}
vector<int> current(SZ(edIx), 0);
for(int i=0; i<SZ(edIx); i++) current[i] = get<0>(Ls[edIx[i]]);
vector<pair<int, vector<int>>> adds;
for(int q=ql; q<qr; q++) {
int t, x, y; tie(t, x, y) = Qs[q];
if(t == 1) {
current[change[x]] = y;
}else{
adds.emplace_back(q, current);
}
}
sort(ALL(adds), [](auto &a, auto &b) { return get<2>(Qs[a.one]) > get<2>(Qs[b.one]); });
int unchangeIx = 0;
uf.init(N);
for(auto vv: adds) {
int q; vector<int> ed; tie(q, ed) = vv;
int st, w; tie(ignore, st, w) = Qs[q];
while(unchangeIx < SZ(ls) && get<0>(ls[unchangeIx]) >= w) {
int c, x, y, ix; tie(c, x, y, ix) = ls[unchangeIx++];
if(change[ix] != -1) continue;
uf.merge(x, y, false);
}
for(int i=0; i<SZ(ed); i++) {
if(ed[i] >= w) {
int x, y; tie(ignore, x, y, ignore) = Ls[edIx[i]];
uf.merge(x, y, true);
}
}
Ans[q] = uf.S[uf.find(st)];
uf.rollback();
}
for(int q=ql; q<qr; q++) {
int t, x, y; tie(t, x, y) = Qs[q];
if(t == 1) {
get<0>(Ls[x]) = y;
}
}
}
for(int i=0; i<Q; i++) {
int t; tie(t, ignore, ignore) = Qs[i];
if(t == 2) printf("%d\n", Ans[i]);
}
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:67:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
67 | int x, y, c; scanf("%d%d%d", &x, &y, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:73:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
73 | int t, x, y; scanf("%d%d%d", &t, &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
23 ms |
1072 KB |
Output is correct |
4 |
Correct |
6 ms |
704 KB |
Output is correct |
5 |
Correct |
12 ms |
700 KB |
Output is correct |
6 |
Correct |
10 ms |
696 KB |
Output is correct |
7 |
Correct |
15 ms |
720 KB |
Output is correct |
8 |
Correct |
17 ms |
720 KB |
Output is correct |
9 |
Correct |
18 ms |
712 KB |
Output is correct |
10 |
Correct |
17 ms |
708 KB |
Output is correct |
11 |
Correct |
17 ms |
708 KB |
Output is correct |
12 |
Correct |
20 ms |
704 KB |
Output is correct |
13 |
Correct |
23 ms |
792 KB |
Output is correct |
14 |
Correct |
21 ms |
792 KB |
Output is correct |
15 |
Correct |
18 ms |
696 KB |
Output is correct |
16 |
Correct |
17 ms |
696 KB |
Output is correct |
17 |
Correct |
17 ms |
704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1514 ms |
5344 KB |
Output is correct |
2 |
Correct |
1519 ms |
5208 KB |
Output is correct |
3 |
Correct |
1526 ms |
5172 KB |
Output is correct |
4 |
Correct |
1602 ms |
5236 KB |
Output is correct |
5 |
Correct |
1604 ms |
5144 KB |
Output is correct |
6 |
Correct |
2136 ms |
5344 KB |
Output is correct |
7 |
Correct |
2119 ms |
5352 KB |
Output is correct |
8 |
Correct |
2093 ms |
5396 KB |
Output is correct |
9 |
Correct |
54 ms |
2156 KB |
Output is correct |
10 |
Correct |
1297 ms |
5480 KB |
Output is correct |
11 |
Correct |
1240 ms |
5232 KB |
Output is correct |
12 |
Correct |
1363 ms |
5380 KB |
Output is correct |
13 |
Correct |
1360 ms |
4880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1190 ms |
4404 KB |
Output is correct |
2 |
Correct |
804 ms |
3312 KB |
Output is correct |
3 |
Correct |
1331 ms |
4628 KB |
Output is correct |
4 |
Correct |
1161 ms |
4372 KB |
Output is correct |
5 |
Correct |
54 ms |
2280 KB |
Output is correct |
6 |
Correct |
1303 ms |
4324 KB |
Output is correct |
7 |
Correct |
1060 ms |
4328 KB |
Output is correct |
8 |
Correct |
971 ms |
4328 KB |
Output is correct |
9 |
Correct |
819 ms |
4136 KB |
Output is correct |
10 |
Correct |
762 ms |
4240 KB |
Output is correct |
11 |
Correct |
851 ms |
4076 KB |
Output is correct |
12 |
Correct |
796 ms |
3952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1973 ms |
7848 KB |
Output is correct |
2 |
Correct |
53 ms |
2156 KB |
Output is correct |
3 |
Correct |
213 ms |
4584 KB |
Output is correct |
4 |
Correct |
127 ms |
4656 KB |
Output is correct |
5 |
Correct |
1203 ms |
7728 KB |
Output is correct |
6 |
Correct |
1888 ms |
7652 KB |
Output is correct |
7 |
Correct |
1230 ms |
7728 KB |
Output is correct |
8 |
Correct |
941 ms |
5096 KB |
Output is correct |
9 |
Correct |
943 ms |
5156 KB |
Output is correct |
10 |
Correct |
959 ms |
5216 KB |
Output is correct |
11 |
Correct |
1466 ms |
6692 KB |
Output is correct |
12 |
Correct |
1411 ms |
6628 KB |
Output is correct |
13 |
Correct |
1452 ms |
6892 KB |
Output is correct |
14 |
Correct |
1161 ms |
7780 KB |
Output is correct |
15 |
Correct |
1198 ms |
7756 KB |
Output is correct |
16 |
Correct |
1948 ms |
7632 KB |
Output is correct |
17 |
Correct |
1959 ms |
7744 KB |
Output is correct |
18 |
Correct |
1942 ms |
7684 KB |
Output is correct |
19 |
Correct |
1936 ms |
7548 KB |
Output is correct |
20 |
Correct |
1605 ms |
7268 KB |
Output is correct |
21 |
Correct |
1663 ms |
7316 KB |
Output is correct |
22 |
Correct |
1840 ms |
7688 KB |
Output is correct |
23 |
Correct |
1182 ms |
7268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1514 ms |
5344 KB |
Output is correct |
2 |
Correct |
1519 ms |
5208 KB |
Output is correct |
3 |
Correct |
1526 ms |
5172 KB |
Output is correct |
4 |
Correct |
1602 ms |
5236 KB |
Output is correct |
5 |
Correct |
1604 ms |
5144 KB |
Output is correct |
6 |
Correct |
2136 ms |
5344 KB |
Output is correct |
7 |
Correct |
2119 ms |
5352 KB |
Output is correct |
8 |
Correct |
2093 ms |
5396 KB |
Output is correct |
9 |
Correct |
54 ms |
2156 KB |
Output is correct |
10 |
Correct |
1297 ms |
5480 KB |
Output is correct |
11 |
Correct |
1240 ms |
5232 KB |
Output is correct |
12 |
Correct |
1363 ms |
5380 KB |
Output is correct |
13 |
Correct |
1360 ms |
4880 KB |
Output is correct |
14 |
Correct |
1190 ms |
4404 KB |
Output is correct |
15 |
Correct |
804 ms |
3312 KB |
Output is correct |
16 |
Correct |
1331 ms |
4628 KB |
Output is correct |
17 |
Correct |
1161 ms |
4372 KB |
Output is correct |
18 |
Correct |
54 ms |
2280 KB |
Output is correct |
19 |
Correct |
1303 ms |
4324 KB |
Output is correct |
20 |
Correct |
1060 ms |
4328 KB |
Output is correct |
21 |
Correct |
971 ms |
4328 KB |
Output is correct |
22 |
Correct |
819 ms |
4136 KB |
Output is correct |
23 |
Correct |
762 ms |
4240 KB |
Output is correct |
24 |
Correct |
851 ms |
4076 KB |
Output is correct |
25 |
Correct |
796 ms |
3952 KB |
Output is correct |
26 |
Correct |
1626 ms |
5204 KB |
Output is correct |
27 |
Correct |
1784 ms |
5348 KB |
Output is correct |
28 |
Correct |
1632 ms |
5272 KB |
Output is correct |
29 |
Correct |
1335 ms |
5096 KB |
Output is correct |
30 |
Correct |
1900 ms |
5216 KB |
Output is correct |
31 |
Correct |
1859 ms |
5352 KB |
Output is correct |
32 |
Correct |
1865 ms |
5136 KB |
Output is correct |
33 |
Correct |
1593 ms |
5224 KB |
Output is correct |
34 |
Correct |
1605 ms |
5096 KB |
Output is correct |
35 |
Correct |
1614 ms |
5096 KB |
Output is correct |
36 |
Correct |
1295 ms |
5084 KB |
Output is correct |
37 |
Correct |
1305 ms |
5168 KB |
Output is correct |
38 |
Correct |
1265 ms |
5076 KB |
Output is correct |
39 |
Correct |
1094 ms |
5032 KB |
Output is correct |
40 |
Correct |
1095 ms |
4976 KB |
Output is correct |
41 |
Correct |
1088 ms |
4968 KB |
Output is correct |
42 |
Correct |
1075 ms |
4868 KB |
Output is correct |
43 |
Correct |
1060 ms |
4968 KB |
Output is correct |
44 |
Correct |
1074 ms |
4896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
23 ms |
1072 KB |
Output is correct |
4 |
Correct |
6 ms |
704 KB |
Output is correct |
5 |
Correct |
12 ms |
700 KB |
Output is correct |
6 |
Correct |
10 ms |
696 KB |
Output is correct |
7 |
Correct |
15 ms |
720 KB |
Output is correct |
8 |
Correct |
17 ms |
720 KB |
Output is correct |
9 |
Correct |
18 ms |
712 KB |
Output is correct |
10 |
Correct |
17 ms |
708 KB |
Output is correct |
11 |
Correct |
17 ms |
708 KB |
Output is correct |
12 |
Correct |
20 ms |
704 KB |
Output is correct |
13 |
Correct |
23 ms |
792 KB |
Output is correct |
14 |
Correct |
21 ms |
792 KB |
Output is correct |
15 |
Correct |
18 ms |
696 KB |
Output is correct |
16 |
Correct |
17 ms |
696 KB |
Output is correct |
17 |
Correct |
17 ms |
704 KB |
Output is correct |
18 |
Correct |
1514 ms |
5344 KB |
Output is correct |
19 |
Correct |
1519 ms |
5208 KB |
Output is correct |
20 |
Correct |
1526 ms |
5172 KB |
Output is correct |
21 |
Correct |
1602 ms |
5236 KB |
Output is correct |
22 |
Correct |
1604 ms |
5144 KB |
Output is correct |
23 |
Correct |
2136 ms |
5344 KB |
Output is correct |
24 |
Correct |
2119 ms |
5352 KB |
Output is correct |
25 |
Correct |
2093 ms |
5396 KB |
Output is correct |
26 |
Correct |
54 ms |
2156 KB |
Output is correct |
27 |
Correct |
1297 ms |
5480 KB |
Output is correct |
28 |
Correct |
1240 ms |
5232 KB |
Output is correct |
29 |
Correct |
1363 ms |
5380 KB |
Output is correct |
30 |
Correct |
1360 ms |
4880 KB |
Output is correct |
31 |
Correct |
1190 ms |
4404 KB |
Output is correct |
32 |
Correct |
804 ms |
3312 KB |
Output is correct |
33 |
Correct |
1331 ms |
4628 KB |
Output is correct |
34 |
Correct |
1161 ms |
4372 KB |
Output is correct |
35 |
Correct |
54 ms |
2280 KB |
Output is correct |
36 |
Correct |
1303 ms |
4324 KB |
Output is correct |
37 |
Correct |
1060 ms |
4328 KB |
Output is correct |
38 |
Correct |
971 ms |
4328 KB |
Output is correct |
39 |
Correct |
819 ms |
4136 KB |
Output is correct |
40 |
Correct |
762 ms |
4240 KB |
Output is correct |
41 |
Correct |
851 ms |
4076 KB |
Output is correct |
42 |
Correct |
796 ms |
3952 KB |
Output is correct |
43 |
Correct |
1973 ms |
7848 KB |
Output is correct |
44 |
Correct |
53 ms |
2156 KB |
Output is correct |
45 |
Correct |
213 ms |
4584 KB |
Output is correct |
46 |
Correct |
127 ms |
4656 KB |
Output is correct |
47 |
Correct |
1203 ms |
7728 KB |
Output is correct |
48 |
Correct |
1888 ms |
7652 KB |
Output is correct |
49 |
Correct |
1230 ms |
7728 KB |
Output is correct |
50 |
Correct |
941 ms |
5096 KB |
Output is correct |
51 |
Correct |
943 ms |
5156 KB |
Output is correct |
52 |
Correct |
959 ms |
5216 KB |
Output is correct |
53 |
Correct |
1466 ms |
6692 KB |
Output is correct |
54 |
Correct |
1411 ms |
6628 KB |
Output is correct |
55 |
Correct |
1452 ms |
6892 KB |
Output is correct |
56 |
Correct |
1161 ms |
7780 KB |
Output is correct |
57 |
Correct |
1198 ms |
7756 KB |
Output is correct |
58 |
Correct |
1948 ms |
7632 KB |
Output is correct |
59 |
Correct |
1959 ms |
7744 KB |
Output is correct |
60 |
Correct |
1942 ms |
7684 KB |
Output is correct |
61 |
Correct |
1936 ms |
7548 KB |
Output is correct |
62 |
Correct |
1605 ms |
7268 KB |
Output is correct |
63 |
Correct |
1663 ms |
7316 KB |
Output is correct |
64 |
Correct |
1840 ms |
7688 KB |
Output is correct |
65 |
Correct |
1182 ms |
7268 KB |
Output is correct |
66 |
Correct |
1626 ms |
5204 KB |
Output is correct |
67 |
Correct |
1784 ms |
5348 KB |
Output is correct |
68 |
Correct |
1632 ms |
5272 KB |
Output is correct |
69 |
Correct |
1335 ms |
5096 KB |
Output is correct |
70 |
Correct |
1900 ms |
5216 KB |
Output is correct |
71 |
Correct |
1859 ms |
5352 KB |
Output is correct |
72 |
Correct |
1865 ms |
5136 KB |
Output is correct |
73 |
Correct |
1593 ms |
5224 KB |
Output is correct |
74 |
Correct |
1605 ms |
5096 KB |
Output is correct |
75 |
Correct |
1614 ms |
5096 KB |
Output is correct |
76 |
Correct |
1295 ms |
5084 KB |
Output is correct |
77 |
Correct |
1305 ms |
5168 KB |
Output is correct |
78 |
Correct |
1265 ms |
5076 KB |
Output is correct |
79 |
Correct |
1094 ms |
5032 KB |
Output is correct |
80 |
Correct |
1095 ms |
4976 KB |
Output is correct |
81 |
Correct |
1088 ms |
4968 KB |
Output is correct |
82 |
Correct |
1075 ms |
4868 KB |
Output is correct |
83 |
Correct |
1060 ms |
4968 KB |
Output is correct |
84 |
Correct |
1074 ms |
4896 KB |
Output is correct |
85 |
Correct |
2386 ms |
7400 KB |
Output is correct |
86 |
Correct |
248 ms |
6944 KB |
Output is correct |
87 |
Correct |
151 ms |
7012 KB |
Output is correct |
88 |
Correct |
1544 ms |
9676 KB |
Output is correct |
89 |
Correct |
2299 ms |
11304 KB |
Output is correct |
90 |
Correct |
1548 ms |
9844 KB |
Output is correct |
91 |
Correct |
1644 ms |
7876 KB |
Output is correct |
92 |
Correct |
1652 ms |
7912 KB |
Output is correct |
93 |
Correct |
2268 ms |
7776 KB |
Output is correct |
94 |
Correct |
1941 ms |
9640 KB |
Output is correct |
95 |
Correct |
1989 ms |
9832 KB |
Output is correct |
96 |
Correct |
2001 ms |
9752 KB |
Output is correct |
97 |
Correct |
1354 ms |
9908 KB |
Output is correct |
98 |
Correct |
1353 ms |
9548 KB |
Output is correct |
99 |
Correct |
2338 ms |
11100 KB |
Output is correct |
100 |
Correct |
2327 ms |
11232 KB |
Output is correct |
101 |
Correct |
2437 ms |
11304 KB |
Output is correct |
102 |
Correct |
2356 ms |
11204 KB |
Output is correct |
103 |
Correct |
2267 ms |
10132 KB |
Output is correct |
104 |
Correct |
2266 ms |
10192 KB |
Output is correct |
105 |
Correct |
1934 ms |
10212 KB |
Output is correct |
106 |
Correct |
1581 ms |
9848 KB |
Output is correct |
107 |
Correct |
1811 ms |
10360 KB |
Output is correct |
108 |
Correct |
2213 ms |
11144 KB |
Output is correct |
109 |
Correct |
1530 ms |
9096 KB |
Output is correct |