#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int MAXN = 1e5 + 12, BS = 1000;
struct edge{
int v, u, w;
}road[MAXN];
struct query{
int t, v, u;
}need[MAXN];
int n, m, q, dsu[MAXN], sz[MAXN], used[MAXN], ans[MAXN];
stack< pair<int, int> > his;
vector< int > bad[MAXN], good, upd, ask;
int getDsu(int x){
if(dsu[x] == x)
return x;
return getDsu(dsu[x]);
}
void merge(int x, int y){
x = getDsu(x), y = getDsu(y);
if(x == y)
return;
if(sz[x] > sz[y])
swap(x, y);
sz[y] += sz[x], dsu[x] = y;
his.push(MP(x, y));
}
void init(){
upd.clear(), good.clear(), ask.clear();
for(int i = 1;i <= n;i++)
dsu[i] = i, sz[i] = 1;
for(int i = 1;i <= m;i++)
used[i] = 0;
while(!his.empty())
his.pop();
}
int main () {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= m;i++){
cin >> road[i].v >> road[i].u >> road[i].w;
}
cin >> q;
for(int i = 0;i < q;i++)
cin >> need[i].t >> need[i].v >> need[i].u;
for(int l = 0;l < q;l += BS){
int r = min(q - 1, l + BS - 1);
init();
for(int i = l;i <= r;i++) if(need[i].t == 1) used[need[i].v] = 1;
for(int i = 1;i <= m;i++) if(!used[i]) good.push_back(i); else upd.push_back(i);
for(int i = l;i <= r;i++){
if(need[i].t == 1){
road[need[i].v].w = need[i].u;
}
else{
ask.push_back(i);
for(int j: upd){
if(road[j].w >= need[i].u)
bad[i].push_back(j);
}
}
}
sort(good.begin(), good.end(), [](int x, int y){return road[x].w > road[y].w;});
sort(ask.begin(), ask.end(), [](int x, int y){return need[x].u > need[y].u;});
int ptr = 0;
for(int i: ask){
while(ptr < good.size() && road[good[ptr]].w >= need[i].u)
merge(road[good[ptr]].u, road[good[ptr]].v), ptr++;
int me = his.size();
for(int z: bad[i])
merge(road[z].u, road[z].v);
ans[i] = (sz[getDsu(need[i].v)]);
while(his.size() > me){
pair<int, int> z = his.top();
his.pop();
dsu[z.X] = z.X, sz[z.Y] -= sz[z.X];
}
}
}
for(int i = 0;i < q;i++)
if(need[i].t == 2)
cout << ans[i] << "\n";
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:76:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | while(ptr < good.size() && road[good[ptr]].w >= need[i].u)
| ~~~~^~~~~~~~~~~~~
bridges.cpp:82:21: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
82 | while(his.size() > me){
| ~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2640 KB |
Output is correct |
3 |
Correct |
47 ms |
8620 KB |
Output is correct |
4 |
Correct |
7 ms |
3004 KB |
Output is correct |
5 |
Correct |
17 ms |
4556 KB |
Output is correct |
6 |
Correct |
13 ms |
4556 KB |
Output is correct |
7 |
Correct |
16 ms |
4524 KB |
Output is correct |
8 |
Correct |
18 ms |
4360 KB |
Output is correct |
9 |
Correct |
24 ms |
5492 KB |
Output is correct |
10 |
Correct |
18 ms |
4516 KB |
Output is correct |
11 |
Correct |
17 ms |
4476 KB |
Output is correct |
12 |
Correct |
20 ms |
4908 KB |
Output is correct |
13 |
Correct |
24 ms |
5396 KB |
Output is correct |
14 |
Correct |
23 ms |
4992 KB |
Output is correct |
15 |
Correct |
19 ms |
4524 KB |
Output is correct |
16 |
Correct |
18 ms |
4812 KB |
Output is correct |
17 |
Correct |
18 ms |
4812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1660 ms |
72916 KB |
Output is correct |
2 |
Correct |
1655 ms |
72996 KB |
Output is correct |
3 |
Correct |
1587 ms |
73528 KB |
Output is correct |
4 |
Correct |
1555 ms |
75424 KB |
Output is correct |
5 |
Correct |
1546 ms |
75928 KB |
Output is correct |
6 |
Correct |
2232 ms |
127540 KB |
Output is correct |
7 |
Correct |
2253 ms |
127056 KB |
Output is correct |
8 |
Correct |
2327 ms |
125020 KB |
Output is correct |
9 |
Correct |
47 ms |
5780 KB |
Output is correct |
10 |
Correct |
1333 ms |
97588 KB |
Output is correct |
11 |
Correct |
1289 ms |
97860 KB |
Output is correct |
12 |
Correct |
1462 ms |
55652 KB |
Output is correct |
13 |
Correct |
1388 ms |
48988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1310 ms |
72636 KB |
Output is correct |
2 |
Correct |
942 ms |
90080 KB |
Output is correct |
3 |
Correct |
1504 ms |
97896 KB |
Output is correct |
4 |
Correct |
1248 ms |
72228 KB |
Output is correct |
5 |
Correct |
46 ms |
4812 KB |
Output is correct |
6 |
Correct |
1416 ms |
92100 KB |
Output is correct |
7 |
Correct |
1136 ms |
64344 KB |
Output is correct |
8 |
Correct |
1008 ms |
48636 KB |
Output is correct |
9 |
Correct |
897 ms |
40572 KB |
Output is correct |
10 |
Correct |
779 ms |
29156 KB |
Output is correct |
11 |
Correct |
809 ms |
37912 KB |
Output is correct |
12 |
Correct |
741 ms |
27768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1857 ms |
7484 KB |
Output is correct |
2 |
Correct |
45 ms |
5760 KB |
Output is correct |
3 |
Correct |
188 ms |
6804 KB |
Output is correct |
4 |
Correct |
89 ms |
6900 KB |
Output is correct |
5 |
Correct |
951 ms |
9844 KB |
Output is correct |
6 |
Correct |
1786 ms |
11256 KB |
Output is correct |
7 |
Correct |
928 ms |
9820 KB |
Output is correct |
8 |
Correct |
896 ms |
8840 KB |
Output is correct |
9 |
Correct |
890 ms |
9076 KB |
Output is correct |
10 |
Correct |
898 ms |
8916 KB |
Output is correct |
11 |
Correct |
1384 ms |
9832 KB |
Output is correct |
12 |
Correct |
1356 ms |
10324 KB |
Output is correct |
13 |
Correct |
1448 ms |
9992 KB |
Output is correct |
14 |
Correct |
877 ms |
9760 KB |
Output is correct |
15 |
Correct |
929 ms |
9704 KB |
Output is correct |
16 |
Correct |
1835 ms |
11168 KB |
Output is correct |
17 |
Correct |
1840 ms |
11404 KB |
Output is correct |
18 |
Correct |
1837 ms |
11232 KB |
Output is correct |
19 |
Correct |
1814 ms |
11180 KB |
Output is correct |
20 |
Correct |
1547 ms |
10436 KB |
Output is correct |
21 |
Correct |
1559 ms |
10436 KB |
Output is correct |
22 |
Correct |
1729 ms |
11056 KB |
Output is correct |
23 |
Correct |
1025 ms |
9240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1660 ms |
72916 KB |
Output is correct |
2 |
Correct |
1655 ms |
72996 KB |
Output is correct |
3 |
Correct |
1587 ms |
73528 KB |
Output is correct |
4 |
Correct |
1555 ms |
75424 KB |
Output is correct |
5 |
Correct |
1546 ms |
75928 KB |
Output is correct |
6 |
Correct |
2232 ms |
127540 KB |
Output is correct |
7 |
Correct |
2253 ms |
127056 KB |
Output is correct |
8 |
Correct |
2327 ms |
125020 KB |
Output is correct |
9 |
Correct |
47 ms |
5780 KB |
Output is correct |
10 |
Correct |
1333 ms |
97588 KB |
Output is correct |
11 |
Correct |
1289 ms |
97860 KB |
Output is correct |
12 |
Correct |
1462 ms |
55652 KB |
Output is correct |
13 |
Correct |
1388 ms |
48988 KB |
Output is correct |
14 |
Correct |
1310 ms |
72636 KB |
Output is correct |
15 |
Correct |
942 ms |
90080 KB |
Output is correct |
16 |
Correct |
1504 ms |
97896 KB |
Output is correct |
17 |
Correct |
1248 ms |
72228 KB |
Output is correct |
18 |
Correct |
46 ms |
4812 KB |
Output is correct |
19 |
Correct |
1416 ms |
92100 KB |
Output is correct |
20 |
Correct |
1136 ms |
64344 KB |
Output is correct |
21 |
Correct |
1008 ms |
48636 KB |
Output is correct |
22 |
Correct |
897 ms |
40572 KB |
Output is correct |
23 |
Correct |
779 ms |
29156 KB |
Output is correct |
24 |
Correct |
809 ms |
37912 KB |
Output is correct |
25 |
Correct |
741 ms |
27768 KB |
Output is correct |
26 |
Correct |
1609 ms |
75680 KB |
Output is correct |
27 |
Correct |
1980 ms |
102496 KB |
Output is correct |
28 |
Correct |
1786 ms |
73892 KB |
Output is correct |
29 |
Correct |
1217 ms |
31152 KB |
Output is correct |
30 |
Correct |
1997 ms |
90004 KB |
Output is correct |
31 |
Correct |
2021 ms |
92268 KB |
Output is correct |
32 |
Correct |
1940 ms |
92612 KB |
Output is correct |
33 |
Correct |
1685 ms |
74108 KB |
Output is correct |
34 |
Correct |
1700 ms |
74312 KB |
Output is correct |
35 |
Correct |
1739 ms |
74592 KB |
Output is correct |
36 |
Correct |
1286 ms |
38088 KB |
Output is correct |
37 |
Correct |
1266 ms |
36756 KB |
Output is correct |
38 |
Correct |
1302 ms |
35220 KB |
Output is correct |
39 |
Correct |
1085 ms |
21308 KB |
Output is correct |
40 |
Correct |
1030 ms |
20612 KB |
Output is correct |
41 |
Correct |
1052 ms |
20064 KB |
Output is correct |
42 |
Correct |
1004 ms |
19656 KB |
Output is correct |
43 |
Correct |
1018 ms |
19200 KB |
Output is correct |
44 |
Correct |
1000 ms |
18612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2640 KB |
Output is correct |
3 |
Correct |
47 ms |
8620 KB |
Output is correct |
4 |
Correct |
7 ms |
3004 KB |
Output is correct |
5 |
Correct |
17 ms |
4556 KB |
Output is correct |
6 |
Correct |
13 ms |
4556 KB |
Output is correct |
7 |
Correct |
16 ms |
4524 KB |
Output is correct |
8 |
Correct |
18 ms |
4360 KB |
Output is correct |
9 |
Correct |
24 ms |
5492 KB |
Output is correct |
10 |
Correct |
18 ms |
4516 KB |
Output is correct |
11 |
Correct |
17 ms |
4476 KB |
Output is correct |
12 |
Correct |
20 ms |
4908 KB |
Output is correct |
13 |
Correct |
24 ms |
5396 KB |
Output is correct |
14 |
Correct |
23 ms |
4992 KB |
Output is correct |
15 |
Correct |
19 ms |
4524 KB |
Output is correct |
16 |
Correct |
18 ms |
4812 KB |
Output is correct |
17 |
Correct |
18 ms |
4812 KB |
Output is correct |
18 |
Correct |
1660 ms |
72916 KB |
Output is correct |
19 |
Correct |
1655 ms |
72996 KB |
Output is correct |
20 |
Correct |
1587 ms |
73528 KB |
Output is correct |
21 |
Correct |
1555 ms |
75424 KB |
Output is correct |
22 |
Correct |
1546 ms |
75928 KB |
Output is correct |
23 |
Correct |
2232 ms |
127540 KB |
Output is correct |
24 |
Correct |
2253 ms |
127056 KB |
Output is correct |
25 |
Correct |
2327 ms |
125020 KB |
Output is correct |
26 |
Correct |
47 ms |
5780 KB |
Output is correct |
27 |
Correct |
1333 ms |
97588 KB |
Output is correct |
28 |
Correct |
1289 ms |
97860 KB |
Output is correct |
29 |
Correct |
1462 ms |
55652 KB |
Output is correct |
30 |
Correct |
1388 ms |
48988 KB |
Output is correct |
31 |
Correct |
1310 ms |
72636 KB |
Output is correct |
32 |
Correct |
942 ms |
90080 KB |
Output is correct |
33 |
Correct |
1504 ms |
97896 KB |
Output is correct |
34 |
Correct |
1248 ms |
72228 KB |
Output is correct |
35 |
Correct |
46 ms |
4812 KB |
Output is correct |
36 |
Correct |
1416 ms |
92100 KB |
Output is correct |
37 |
Correct |
1136 ms |
64344 KB |
Output is correct |
38 |
Correct |
1008 ms |
48636 KB |
Output is correct |
39 |
Correct |
897 ms |
40572 KB |
Output is correct |
40 |
Correct |
779 ms |
29156 KB |
Output is correct |
41 |
Correct |
809 ms |
37912 KB |
Output is correct |
42 |
Correct |
741 ms |
27768 KB |
Output is correct |
43 |
Correct |
1857 ms |
7484 KB |
Output is correct |
44 |
Correct |
45 ms |
5760 KB |
Output is correct |
45 |
Correct |
188 ms |
6804 KB |
Output is correct |
46 |
Correct |
89 ms |
6900 KB |
Output is correct |
47 |
Correct |
951 ms |
9844 KB |
Output is correct |
48 |
Correct |
1786 ms |
11256 KB |
Output is correct |
49 |
Correct |
928 ms |
9820 KB |
Output is correct |
50 |
Correct |
896 ms |
8840 KB |
Output is correct |
51 |
Correct |
890 ms |
9076 KB |
Output is correct |
52 |
Correct |
898 ms |
8916 KB |
Output is correct |
53 |
Correct |
1384 ms |
9832 KB |
Output is correct |
54 |
Correct |
1356 ms |
10324 KB |
Output is correct |
55 |
Correct |
1448 ms |
9992 KB |
Output is correct |
56 |
Correct |
877 ms |
9760 KB |
Output is correct |
57 |
Correct |
929 ms |
9704 KB |
Output is correct |
58 |
Correct |
1835 ms |
11168 KB |
Output is correct |
59 |
Correct |
1840 ms |
11404 KB |
Output is correct |
60 |
Correct |
1837 ms |
11232 KB |
Output is correct |
61 |
Correct |
1814 ms |
11180 KB |
Output is correct |
62 |
Correct |
1547 ms |
10436 KB |
Output is correct |
63 |
Correct |
1559 ms |
10436 KB |
Output is correct |
64 |
Correct |
1729 ms |
11056 KB |
Output is correct |
65 |
Correct |
1025 ms |
9240 KB |
Output is correct |
66 |
Correct |
1609 ms |
75680 KB |
Output is correct |
67 |
Correct |
1980 ms |
102496 KB |
Output is correct |
68 |
Correct |
1786 ms |
73892 KB |
Output is correct |
69 |
Correct |
1217 ms |
31152 KB |
Output is correct |
70 |
Correct |
1997 ms |
90004 KB |
Output is correct |
71 |
Correct |
2021 ms |
92268 KB |
Output is correct |
72 |
Correct |
1940 ms |
92612 KB |
Output is correct |
73 |
Correct |
1685 ms |
74108 KB |
Output is correct |
74 |
Correct |
1700 ms |
74312 KB |
Output is correct |
75 |
Correct |
1739 ms |
74592 KB |
Output is correct |
76 |
Correct |
1286 ms |
38088 KB |
Output is correct |
77 |
Correct |
1266 ms |
36756 KB |
Output is correct |
78 |
Correct |
1302 ms |
35220 KB |
Output is correct |
79 |
Correct |
1085 ms |
21308 KB |
Output is correct |
80 |
Correct |
1030 ms |
20612 KB |
Output is correct |
81 |
Correct |
1052 ms |
20064 KB |
Output is correct |
82 |
Correct |
1004 ms |
19656 KB |
Output is correct |
83 |
Correct |
1018 ms |
19200 KB |
Output is correct |
84 |
Correct |
1000 ms |
18612 KB |
Output is correct |
85 |
Correct |
2444 ms |
78036 KB |
Output is correct |
86 |
Correct |
233 ms |
13308 KB |
Output is correct |
87 |
Correct |
154 ms |
17712 KB |
Output is correct |
88 |
Correct |
1539 ms |
89196 KB |
Output is correct |
89 |
Correct |
2433 ms |
76700 KB |
Output is correct |
90 |
Correct |
1555 ms |
96820 KB |
Output is correct |
91 |
Correct |
1727 ms |
75728 KB |
Output is correct |
92 |
Correct |
1695 ms |
75564 KB |
Output is correct |
93 |
Correct |
2425 ms |
112760 KB |
Output is correct |
94 |
Correct |
2133 ms |
76736 KB |
Output is correct |
95 |
Correct |
2133 ms |
76580 KB |
Output is correct |
96 |
Correct |
2518 ms |
115944 KB |
Output is correct |
97 |
Correct |
1156 ms |
42852 KB |
Output is correct |
98 |
Correct |
1228 ms |
39424 KB |
Output is correct |
99 |
Correct |
2540 ms |
78940 KB |
Output is correct |
100 |
Correct |
2471 ms |
77612 KB |
Output is correct |
101 |
Correct |
2545 ms |
77784 KB |
Output is correct |
102 |
Correct |
2569 ms |
77804 KB |
Output is correct |
103 |
Correct |
2717 ms |
120580 KB |
Output is correct |
104 |
Correct |
2736 ms |
120436 KB |
Output is correct |
105 |
Correct |
1963 ms |
50280 KB |
Output is correct |
106 |
Correct |
1623 ms |
30232 KB |
Output is correct |
107 |
Correct |
1891 ms |
57056 KB |
Output is correct |
108 |
Correct |
2534 ms |
112924 KB |
Output is correct |
109 |
Correct |
1933 ms |
115476 KB |
Output is correct |