#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
const int maxn = 1e5 + 5;
ll u[maxn], v[maxn], w[maxn];
ll t[maxn], x[maxn], y[maxn], ch[maxn]; // [bridge, new weight] or [start, car weight]
ll ans[maxn];
vector<int> to_join[maxn];
int n, m, q;
const int b = 1200;
struct dsu_save{
int u, rku, v, rkv;
dsu_save(){}
dsu_save(int _u, int _rku, int _v, int _rkv) : u(_u), rku(_rku), v(_v), rkv(_rkv){}
};
struct DSU{
vector<int> par, siz;
int n;
stack<int> stk;
DSU(){}
DSU(int _n) : n(_n){}
void init(){
siz = vector<int>(n, 1);
par.resize(n);
for(int i = 0; i < n; i++) par[i] = i;
}
int root(int x){
return x == par[x] ? x : root(par[x]);
}
void unite(int x, int y){
x = root(x);
y = root(y);
if(x == y) return;
if(siz[x] > siz[y]) swap(x, y);
stk.push(x);
par[x] = y;
siz[y] += siz[x];
}
void roll_back(int sz){
while(stk.size() > sz){
auto u = stk.top(); stk.pop();
siz[par[u]] -= siz[u];
par[u] = u;
}
}
};
int main(void){
fastio;
cin>>n>>m;
DSU dsu(n + 1);
for(int i = 1; i <= m; i++){
cin >> u[i] >> v[i] >> w[i];
}
cin>>q;
for(int i = 1; i <= q; i++){
cin >> t[i] >> x[i] >> y[i];
}
for(int l = 1; l <= q; l += b){
int r = min(q + 1, l + b);
fill(ch, ch + maxn, false);
dsu.init();
vector<int> ask, upd, unchanged;
for(int i = l; i < r; i++){
if(t[i] == 1){
ch[x[i]] = true;
upd.pb(i);
}
else ask.pb(i);
}
for(int i = 1; i <= m; i++){
if(!ch[i]) unchanged.pb(i);
}
for(int i = l; i < r; i++){
if(t[i] == 1) w[x[i]] = y[i];
else{
to_join[i].clear();
for(auto j : upd){
if(w[x[j]] >= y[i]) to_join[i].pb(x[j]);
}
}
}
sort(ask.begin(), ask.end(), [](int a, int b){ return y[a] > y[b];});
sort(unchanged.begin(), unchanged.end(), [](int a, int b){ return w[a] > w[b];});
// processing queries
int unptr = 0;
for(auto i : ask){
while(unptr < unchanged.size() && w[unchanged[unptr]] >= y[i]){ // no need to roll back
dsu.unite(u[unchanged[unptr]], v[unchanged[unptr]]);
unptr++;
}
int prev_sz = dsu.stk.size();
for(auto j : to_join[i]){
dsu.unite(u[j], v[j]);
}
ans[i] = dsu.siz[dsu.root(x[i])];
dsu.roll_back(prev_sz);
}
}
for(int i = 1; i <= q; i++) if(t[i] == 2) cout << ans[i] << "\n";
}
Compilation message
bridges.cpp: In member function 'void DSU::roll_back(int)':
bridges.cpp:44:20: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | while(stk.size() > sz){
| ~~~~~~~~~~~^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:93:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | while(unptr < unchanged.size() && w[unchanged[unptr]] >= y[i]){ // no need to roll back
| ~~~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
1 ms |
3412 KB |
Output is correct |
3 |
Correct |
38 ms |
12148 KB |
Output is correct |
4 |
Correct |
4 ms |
3796 KB |
Output is correct |
5 |
Correct |
34 ms |
14152 KB |
Output is correct |
6 |
Correct |
25 ms |
14504 KB |
Output is correct |
7 |
Correct |
28 ms |
15308 KB |
Output is correct |
8 |
Correct |
35 ms |
11492 KB |
Output is correct |
9 |
Correct |
38 ms |
23100 KB |
Output is correct |
10 |
Correct |
37 ms |
12780 KB |
Output is correct |
11 |
Correct |
37 ms |
12096 KB |
Output is correct |
12 |
Correct |
46 ms |
15200 KB |
Output is correct |
13 |
Correct |
41 ms |
13268 KB |
Output is correct |
14 |
Correct |
37 ms |
11708 KB |
Output is correct |
15 |
Correct |
42 ms |
12808 KB |
Output is correct |
16 |
Correct |
31 ms |
18200 KB |
Output is correct |
17 |
Correct |
32 ms |
15980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
986 ms |
112944 KB |
Output is correct |
2 |
Correct |
1006 ms |
112176 KB |
Output is correct |
3 |
Correct |
1022 ms |
112596 KB |
Output is correct |
4 |
Correct |
1022 ms |
112000 KB |
Output is correct |
5 |
Correct |
1004 ms |
112728 KB |
Output is correct |
6 |
Correct |
1221 ms |
225836 KB |
Output is correct |
7 |
Correct |
1197 ms |
226636 KB |
Output is correct |
8 |
Correct |
1234 ms |
226388 KB |
Output is correct |
9 |
Correct |
30 ms |
6732 KB |
Output is correct |
10 |
Correct |
663 ms |
175972 KB |
Output is correct |
11 |
Correct |
636 ms |
145620 KB |
Output is correct |
12 |
Correct |
834 ms |
83632 KB |
Output is correct |
13 |
Correct |
807 ms |
105132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
772 ms |
106448 KB |
Output is correct |
2 |
Correct |
509 ms |
154852 KB |
Output is correct |
3 |
Correct |
821 ms |
164372 KB |
Output is correct |
4 |
Correct |
746 ms |
105528 KB |
Output is correct |
5 |
Correct |
31 ms |
6740 KB |
Output is correct |
6 |
Correct |
839 ms |
132992 KB |
Output is correct |
7 |
Correct |
713 ms |
95836 KB |
Output is correct |
8 |
Correct |
628 ms |
73684 KB |
Output is correct |
9 |
Correct |
515 ms |
58372 KB |
Output is correct |
10 |
Correct |
486 ms |
45736 KB |
Output is correct |
11 |
Correct |
561 ms |
56792 KB |
Output is correct |
12 |
Correct |
541 ms |
45188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1288 ms |
27472 KB |
Output is correct |
2 |
Correct |
30 ms |
6740 KB |
Output is correct |
3 |
Correct |
157 ms |
7112 KB |
Output is correct |
4 |
Correct |
73 ms |
7012 KB |
Output is correct |
5 |
Correct |
659 ms |
27740 KB |
Output is correct |
6 |
Correct |
1257 ms |
27412 KB |
Output is correct |
7 |
Correct |
655 ms |
27432 KB |
Output is correct |
8 |
Correct |
590 ms |
25940 KB |
Output is correct |
9 |
Correct |
569 ms |
25868 KB |
Output is correct |
10 |
Correct |
569 ms |
26028 KB |
Output is correct |
11 |
Correct |
928 ms |
26896 KB |
Output is correct |
12 |
Correct |
915 ms |
26940 KB |
Output is correct |
13 |
Correct |
962 ms |
27112 KB |
Output is correct |
14 |
Correct |
605 ms |
27612 KB |
Output is correct |
15 |
Correct |
640 ms |
27480 KB |
Output is correct |
16 |
Correct |
1309 ms |
27600 KB |
Output is correct |
17 |
Correct |
1283 ms |
27616 KB |
Output is correct |
18 |
Correct |
1269 ms |
27744 KB |
Output is correct |
19 |
Correct |
1289 ms |
27832 KB |
Output is correct |
20 |
Correct |
1062 ms |
27352 KB |
Output is correct |
21 |
Correct |
1066 ms |
27436 KB |
Output is correct |
22 |
Correct |
1210 ms |
27308 KB |
Output is correct |
23 |
Correct |
688 ms |
25524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
986 ms |
112944 KB |
Output is correct |
2 |
Correct |
1006 ms |
112176 KB |
Output is correct |
3 |
Correct |
1022 ms |
112596 KB |
Output is correct |
4 |
Correct |
1022 ms |
112000 KB |
Output is correct |
5 |
Correct |
1004 ms |
112728 KB |
Output is correct |
6 |
Correct |
1221 ms |
225836 KB |
Output is correct |
7 |
Correct |
1197 ms |
226636 KB |
Output is correct |
8 |
Correct |
1234 ms |
226388 KB |
Output is correct |
9 |
Correct |
30 ms |
6732 KB |
Output is correct |
10 |
Correct |
663 ms |
175972 KB |
Output is correct |
11 |
Correct |
636 ms |
145620 KB |
Output is correct |
12 |
Correct |
834 ms |
83632 KB |
Output is correct |
13 |
Correct |
807 ms |
105132 KB |
Output is correct |
14 |
Correct |
772 ms |
106448 KB |
Output is correct |
15 |
Correct |
509 ms |
154852 KB |
Output is correct |
16 |
Correct |
821 ms |
164372 KB |
Output is correct |
17 |
Correct |
746 ms |
105528 KB |
Output is correct |
18 |
Correct |
31 ms |
6740 KB |
Output is correct |
19 |
Correct |
839 ms |
132992 KB |
Output is correct |
20 |
Correct |
713 ms |
95836 KB |
Output is correct |
21 |
Correct |
628 ms |
73684 KB |
Output is correct |
22 |
Correct |
515 ms |
58372 KB |
Output is correct |
23 |
Correct |
486 ms |
45736 KB |
Output is correct |
24 |
Correct |
561 ms |
56792 KB |
Output is correct |
25 |
Correct |
541 ms |
45188 KB |
Output is correct |
26 |
Correct |
1022 ms |
112232 KB |
Output is correct |
27 |
Correct |
1060 ms |
171496 KB |
Output is correct |
28 |
Correct |
975 ms |
110460 KB |
Output is correct |
29 |
Correct |
758 ms |
54056 KB |
Output is correct |
30 |
Correct |
1094 ms |
143168 KB |
Output is correct |
31 |
Correct |
1118 ms |
148568 KB |
Output is correct |
32 |
Correct |
1152 ms |
150120 KB |
Output is correct |
33 |
Correct |
1038 ms |
108984 KB |
Output is correct |
34 |
Correct |
995 ms |
109860 KB |
Output is correct |
35 |
Correct |
995 ms |
109860 KB |
Output is correct |
36 |
Correct |
791 ms |
62656 KB |
Output is correct |
37 |
Correct |
796 ms |
60672 KB |
Output is correct |
38 |
Correct |
775 ms |
58804 KB |
Output is correct |
39 |
Correct |
663 ms |
39848 KB |
Output is correct |
40 |
Correct |
654 ms |
38932 KB |
Output is correct |
41 |
Correct |
664 ms |
38428 KB |
Output is correct |
42 |
Correct |
635 ms |
37656 KB |
Output is correct |
43 |
Correct |
635 ms |
36908 KB |
Output is correct |
44 |
Correct |
656 ms |
36332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
1 ms |
3412 KB |
Output is correct |
3 |
Correct |
38 ms |
12148 KB |
Output is correct |
4 |
Correct |
4 ms |
3796 KB |
Output is correct |
5 |
Correct |
34 ms |
14152 KB |
Output is correct |
6 |
Correct |
25 ms |
14504 KB |
Output is correct |
7 |
Correct |
28 ms |
15308 KB |
Output is correct |
8 |
Correct |
35 ms |
11492 KB |
Output is correct |
9 |
Correct |
38 ms |
23100 KB |
Output is correct |
10 |
Correct |
37 ms |
12780 KB |
Output is correct |
11 |
Correct |
37 ms |
12096 KB |
Output is correct |
12 |
Correct |
46 ms |
15200 KB |
Output is correct |
13 |
Correct |
41 ms |
13268 KB |
Output is correct |
14 |
Correct |
37 ms |
11708 KB |
Output is correct |
15 |
Correct |
42 ms |
12808 KB |
Output is correct |
16 |
Correct |
31 ms |
18200 KB |
Output is correct |
17 |
Correct |
32 ms |
15980 KB |
Output is correct |
18 |
Correct |
986 ms |
112944 KB |
Output is correct |
19 |
Correct |
1006 ms |
112176 KB |
Output is correct |
20 |
Correct |
1022 ms |
112596 KB |
Output is correct |
21 |
Correct |
1022 ms |
112000 KB |
Output is correct |
22 |
Correct |
1004 ms |
112728 KB |
Output is correct |
23 |
Correct |
1221 ms |
225836 KB |
Output is correct |
24 |
Correct |
1197 ms |
226636 KB |
Output is correct |
25 |
Correct |
1234 ms |
226388 KB |
Output is correct |
26 |
Correct |
30 ms |
6732 KB |
Output is correct |
27 |
Correct |
663 ms |
175972 KB |
Output is correct |
28 |
Correct |
636 ms |
145620 KB |
Output is correct |
29 |
Correct |
834 ms |
83632 KB |
Output is correct |
30 |
Correct |
807 ms |
105132 KB |
Output is correct |
31 |
Correct |
772 ms |
106448 KB |
Output is correct |
32 |
Correct |
509 ms |
154852 KB |
Output is correct |
33 |
Correct |
821 ms |
164372 KB |
Output is correct |
34 |
Correct |
746 ms |
105528 KB |
Output is correct |
35 |
Correct |
31 ms |
6740 KB |
Output is correct |
36 |
Correct |
839 ms |
132992 KB |
Output is correct |
37 |
Correct |
713 ms |
95836 KB |
Output is correct |
38 |
Correct |
628 ms |
73684 KB |
Output is correct |
39 |
Correct |
515 ms |
58372 KB |
Output is correct |
40 |
Correct |
486 ms |
45736 KB |
Output is correct |
41 |
Correct |
561 ms |
56792 KB |
Output is correct |
42 |
Correct |
541 ms |
45188 KB |
Output is correct |
43 |
Correct |
1288 ms |
27472 KB |
Output is correct |
44 |
Correct |
30 ms |
6740 KB |
Output is correct |
45 |
Correct |
157 ms |
7112 KB |
Output is correct |
46 |
Correct |
73 ms |
7012 KB |
Output is correct |
47 |
Correct |
659 ms |
27740 KB |
Output is correct |
48 |
Correct |
1257 ms |
27412 KB |
Output is correct |
49 |
Correct |
655 ms |
27432 KB |
Output is correct |
50 |
Correct |
590 ms |
25940 KB |
Output is correct |
51 |
Correct |
569 ms |
25868 KB |
Output is correct |
52 |
Correct |
569 ms |
26028 KB |
Output is correct |
53 |
Correct |
928 ms |
26896 KB |
Output is correct |
54 |
Correct |
915 ms |
26940 KB |
Output is correct |
55 |
Correct |
962 ms |
27112 KB |
Output is correct |
56 |
Correct |
605 ms |
27612 KB |
Output is correct |
57 |
Correct |
640 ms |
27480 KB |
Output is correct |
58 |
Correct |
1309 ms |
27600 KB |
Output is correct |
59 |
Correct |
1283 ms |
27616 KB |
Output is correct |
60 |
Correct |
1269 ms |
27744 KB |
Output is correct |
61 |
Correct |
1289 ms |
27832 KB |
Output is correct |
62 |
Correct |
1062 ms |
27352 KB |
Output is correct |
63 |
Correct |
1066 ms |
27436 KB |
Output is correct |
64 |
Correct |
1210 ms |
27308 KB |
Output is correct |
65 |
Correct |
688 ms |
25524 KB |
Output is correct |
66 |
Correct |
1022 ms |
112232 KB |
Output is correct |
67 |
Correct |
1060 ms |
171496 KB |
Output is correct |
68 |
Correct |
975 ms |
110460 KB |
Output is correct |
69 |
Correct |
758 ms |
54056 KB |
Output is correct |
70 |
Correct |
1094 ms |
143168 KB |
Output is correct |
71 |
Correct |
1118 ms |
148568 KB |
Output is correct |
72 |
Correct |
1152 ms |
150120 KB |
Output is correct |
73 |
Correct |
1038 ms |
108984 KB |
Output is correct |
74 |
Correct |
995 ms |
109860 KB |
Output is correct |
75 |
Correct |
995 ms |
109860 KB |
Output is correct |
76 |
Correct |
791 ms |
62656 KB |
Output is correct |
77 |
Correct |
796 ms |
60672 KB |
Output is correct |
78 |
Correct |
775 ms |
58804 KB |
Output is correct |
79 |
Correct |
663 ms |
39848 KB |
Output is correct |
80 |
Correct |
654 ms |
38932 KB |
Output is correct |
81 |
Correct |
664 ms |
38428 KB |
Output is correct |
82 |
Correct |
635 ms |
37656 KB |
Output is correct |
83 |
Correct |
635 ms |
36908 KB |
Output is correct |
84 |
Correct |
656 ms |
36332 KB |
Output is correct |
85 |
Correct |
1617 ms |
114436 KB |
Output is correct |
86 |
Correct |
202 ms |
15948 KB |
Output is correct |
87 |
Correct |
120 ms |
26784 KB |
Output is correct |
88 |
Correct |
936 ms |
140936 KB |
Output is correct |
89 |
Correct |
1617 ms |
113024 KB |
Output is correct |
90 |
Correct |
932 ms |
142360 KB |
Output is correct |
91 |
Correct |
1010 ms |
112812 KB |
Output is correct |
92 |
Correct |
1016 ms |
112552 KB |
Output is correct |
93 |
Correct |
1232 ms |
227240 KB |
Output is correct |
94 |
Correct |
1364 ms |
114144 KB |
Output is correct |
95 |
Correct |
1362 ms |
114356 KB |
Output is correct |
96 |
Correct |
1535 ms |
227164 KB |
Output is correct |
97 |
Correct |
777 ms |
65916 KB |
Output is correct |
98 |
Correct |
768 ms |
72736 KB |
Output is correct |
99 |
Correct |
1687 ms |
116892 KB |
Output is correct |
100 |
Correct |
1643 ms |
115368 KB |
Output is correct |
101 |
Correct |
1646 ms |
114964 KB |
Output is correct |
102 |
Correct |
1654 ms |
114516 KB |
Output is correct |
103 |
Correct |
1616 ms |
227912 KB |
Output is correct |
104 |
Correct |
1577 ms |
228112 KB |
Output is correct |
105 |
Correct |
1252 ms |
107528 KB |
Output is correct |
106 |
Correct |
1088 ms |
67808 KB |
Output is correct |
107 |
Correct |
1243 ms |
82556 KB |
Output is correct |
108 |
Correct |
1631 ms |
170080 KB |
Output is correct |
109 |
Correct |
1079 ms |
224224 KB |
Output is correct |