# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
884208 |
2023-12-06T18:15:41 Z |
Hakiers |
Bridges (APIO19_bridges) |
C++17 |
|
1627 ms |
12388 KB |
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 7;
constexpr int SQRT = 1000;
struct edg{
int u, v, w;
};
struct que{
int t, x, y;
};
edg edges[MAXN];
que queries[MAXN];
int sajz[MAXN];
int rep[MAXN];
int res[MAXN];
vector<int> last[SQRT+1];
stack<int> S;
int n, m, q;
int Find(int a){
if(a == rep[a]) return a;
return Find(rep[a]);
}
void Union(int a, int b){
a = Find(a);
b = Find(b);
if(a == b) return;
if(sajz[a] < sajz[b]) swap(a, b);
S.push(b);
rep[b] = a;
sajz[a] += sajz[b];
}
void roll_back(int x){
while(S.size() > x){
int b = S.top();
S.pop();
sajz[Find(b)] -= sajz[b];
rep[b] = b;
}
}
void resetdsu(){
for(int i = 1; i <= n; i++){
sajz[i] = 1;
rep[i] = i;
}
while(S.size()) S.pop();
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++)
cin >> edges[i].u >> edges[i].v >> edges[i].w;
cin >> q;
for(int i = 1; i <= q; i++)
cin >> queries[i].t >> queries[i].x >> queries[i].y;
for(int l = 1; l <= q; l += SQRT){
int r = min(q, l + SQRT - 1);
resetdsu();
vector<bool> changed(m+1, false);
vector<int> ans;
vector<int> act;
for(int i = l; i <= r; i++){
if(queries[i].t == 1){
changed[queries[i].x] = 1;
act.push_back(queries[i].x);
}
else ans.push_back(i);
}
vector<int> unchanged;
for(int i = 1; i <= m; i++)
if(!changed[i]) unchanged.push_back(i);
for(int i = l; i <= r; i++){
if(queries[i].t == 1)
edges[queries[i].x].w = queries[i].y;
else{
last[i-l].clear();
last[i-l].shrink_to_fit();
for(auto z : act)
if(edges[z].w >= queries[i].y) last[i-l].push_back(z);
}
}
sort(unchanged.begin(), unchanged.end(), [&](int a, int b) { return edges[a].w > edges[b].w;});
sort(ans.begin(), ans.end(), [&](int a, int b) { return queries[a].y > queries[b].y;});
int it = 0;
for(auto i : ans){
while(it < unchanged.size() && edges[unchanged[it]].w >= queries[i].y){
Union(edges[unchanged[it]].u, edges[unchanged[it]].v);
++it;
}
int prev_lenght = S.size();
for(auto z : last[i - l])
Union(edges[z].u, edges[z].v);
res[i] = sajz[Find(queries[i].x)];
roll_back(prev_lenght);
}
}
for(int i = 1; i <= q; i++)
if(queries[i].t == 2) cout << res[i] << "\n";
}
Compilation message
bridges.cpp: In function 'void roll_back(int)':
bridges.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
36 | while(S.size() > x){
| ~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:100:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | while(it < unchanged.size() && edges[unchanged[it]].w >= queries[i].y){
| ~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
24 ms |
3932 KB |
Output is correct |
4 |
Correct |
3 ms |
2396 KB |
Output is correct |
5 |
Correct |
25 ms |
4308 KB |
Output is correct |
6 |
Correct |
18 ms |
4444 KB |
Output is correct |
7 |
Correct |
20 ms |
4700 KB |
Output is correct |
8 |
Correct |
28 ms |
3676 KB |
Output is correct |
9 |
Correct |
31 ms |
6136 KB |
Output is correct |
10 |
Correct |
27 ms |
3988 KB |
Output is correct |
11 |
Correct |
28 ms |
3932 KB |
Output is correct |
12 |
Correct |
34 ms |
4684 KB |
Output is correct |
13 |
Correct |
32 ms |
4124 KB |
Output is correct |
14 |
Correct |
30 ms |
3924 KB |
Output is correct |
15 |
Correct |
36 ms |
4252 KB |
Output is correct |
16 |
Correct |
29 ms |
5208 KB |
Output is correct |
17 |
Correct |
25 ms |
4696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
881 ms |
5540 KB |
Output is correct |
2 |
Correct |
892 ms |
5516 KB |
Output is correct |
3 |
Correct |
864 ms |
5496 KB |
Output is correct |
4 |
Correct |
897 ms |
5640 KB |
Output is correct |
5 |
Correct |
880 ms |
5772 KB |
Output is correct |
6 |
Correct |
1061 ms |
8176 KB |
Output is correct |
7 |
Correct |
1033 ms |
8272 KB |
Output is correct |
8 |
Correct |
1029 ms |
8132 KB |
Output is correct |
9 |
Correct |
25 ms |
2900 KB |
Output is correct |
10 |
Correct |
549 ms |
6748 KB |
Output is correct |
11 |
Correct |
518 ms |
6440 KB |
Output is correct |
12 |
Correct |
716 ms |
4784 KB |
Output is correct |
13 |
Correct |
710 ms |
7976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
644 ms |
5052 KB |
Output is correct |
2 |
Correct |
399 ms |
6152 KB |
Output is correct |
3 |
Correct |
686 ms |
6480 KB |
Output is correct |
4 |
Correct |
630 ms |
5036 KB |
Output is correct |
5 |
Correct |
25 ms |
2796 KB |
Output is correct |
6 |
Correct |
688 ms |
5384 KB |
Output is correct |
7 |
Correct |
608 ms |
5316 KB |
Output is correct |
8 |
Correct |
562 ms |
5072 KB |
Output is correct |
9 |
Correct |
470 ms |
4324 KB |
Output is correct |
10 |
Correct |
443 ms |
4292 KB |
Output is correct |
11 |
Correct |
481 ms |
7132 KB |
Output is correct |
12 |
Correct |
443 ms |
5920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1294 ms |
5440 KB |
Output is correct |
2 |
Correct |
31 ms |
4184 KB |
Output is correct |
3 |
Correct |
140 ms |
6740 KB |
Output is correct |
4 |
Correct |
60 ms |
6600 KB |
Output is correct |
5 |
Correct |
653 ms |
7812 KB |
Output is correct |
6 |
Correct |
1220 ms |
9392 KB |
Output is correct |
7 |
Correct |
602 ms |
7724 KB |
Output is correct |
8 |
Correct |
580 ms |
6744 KB |
Output is correct |
9 |
Correct |
569 ms |
6988 KB |
Output is correct |
10 |
Correct |
611 ms |
6672 KB |
Output is correct |
11 |
Correct |
920 ms |
8108 KB |
Output is correct |
12 |
Correct |
915 ms |
8252 KB |
Output is correct |
13 |
Correct |
928 ms |
8432 KB |
Output is correct |
14 |
Correct |
555 ms |
7660 KB |
Output is correct |
15 |
Correct |
575 ms |
7768 KB |
Output is correct |
16 |
Correct |
1397 ms |
9228 KB |
Output is correct |
17 |
Correct |
1281 ms |
9040 KB |
Output is correct |
18 |
Correct |
1251 ms |
9160 KB |
Output is correct |
19 |
Correct |
1295 ms |
9152 KB |
Output is correct |
20 |
Correct |
1044 ms |
8496 KB |
Output is correct |
21 |
Correct |
1042 ms |
8408 KB |
Output is correct |
22 |
Correct |
1206 ms |
9116 KB |
Output is correct |
23 |
Correct |
704 ms |
7200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
881 ms |
5540 KB |
Output is correct |
2 |
Correct |
892 ms |
5516 KB |
Output is correct |
3 |
Correct |
864 ms |
5496 KB |
Output is correct |
4 |
Correct |
897 ms |
5640 KB |
Output is correct |
5 |
Correct |
880 ms |
5772 KB |
Output is correct |
6 |
Correct |
1061 ms |
8176 KB |
Output is correct |
7 |
Correct |
1033 ms |
8272 KB |
Output is correct |
8 |
Correct |
1029 ms |
8132 KB |
Output is correct |
9 |
Correct |
25 ms |
2900 KB |
Output is correct |
10 |
Correct |
549 ms |
6748 KB |
Output is correct |
11 |
Correct |
518 ms |
6440 KB |
Output is correct |
12 |
Correct |
716 ms |
4784 KB |
Output is correct |
13 |
Correct |
710 ms |
7976 KB |
Output is correct |
14 |
Correct |
644 ms |
5052 KB |
Output is correct |
15 |
Correct |
399 ms |
6152 KB |
Output is correct |
16 |
Correct |
686 ms |
6480 KB |
Output is correct |
17 |
Correct |
630 ms |
5036 KB |
Output is correct |
18 |
Correct |
25 ms |
2796 KB |
Output is correct |
19 |
Correct |
688 ms |
5384 KB |
Output is correct |
20 |
Correct |
608 ms |
5316 KB |
Output is correct |
21 |
Correct |
562 ms |
5072 KB |
Output is correct |
22 |
Correct |
470 ms |
4324 KB |
Output is correct |
23 |
Correct |
443 ms |
4292 KB |
Output is correct |
24 |
Correct |
481 ms |
7132 KB |
Output is correct |
25 |
Correct |
443 ms |
5920 KB |
Output is correct |
26 |
Correct |
874 ms |
5536 KB |
Output is correct |
27 |
Correct |
962 ms |
6716 KB |
Output is correct |
28 |
Correct |
946 ms |
5460 KB |
Output is correct |
29 |
Correct |
736 ms |
4888 KB |
Output is correct |
30 |
Correct |
958 ms |
6200 KB |
Output is correct |
31 |
Correct |
1000 ms |
6404 KB |
Output is correct |
32 |
Correct |
1008 ms |
6384 KB |
Output is correct |
33 |
Correct |
898 ms |
5480 KB |
Output is correct |
34 |
Correct |
896 ms |
5516 KB |
Output is correct |
35 |
Correct |
895 ms |
5468 KB |
Output is correct |
36 |
Correct |
746 ms |
4744 KB |
Output is correct |
37 |
Correct |
775 ms |
4688 KB |
Output is correct |
38 |
Correct |
728 ms |
4692 KB |
Output is correct |
39 |
Correct |
645 ms |
4252 KB |
Output is correct |
40 |
Correct |
641 ms |
4556 KB |
Output is correct |
41 |
Correct |
649 ms |
4212 KB |
Output is correct |
42 |
Correct |
625 ms |
5208 KB |
Output is correct |
43 |
Correct |
641 ms |
5296 KB |
Output is correct |
44 |
Correct |
626 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
24 ms |
3932 KB |
Output is correct |
4 |
Correct |
3 ms |
2396 KB |
Output is correct |
5 |
Correct |
25 ms |
4308 KB |
Output is correct |
6 |
Correct |
18 ms |
4444 KB |
Output is correct |
7 |
Correct |
20 ms |
4700 KB |
Output is correct |
8 |
Correct |
28 ms |
3676 KB |
Output is correct |
9 |
Correct |
31 ms |
6136 KB |
Output is correct |
10 |
Correct |
27 ms |
3988 KB |
Output is correct |
11 |
Correct |
28 ms |
3932 KB |
Output is correct |
12 |
Correct |
34 ms |
4684 KB |
Output is correct |
13 |
Correct |
32 ms |
4124 KB |
Output is correct |
14 |
Correct |
30 ms |
3924 KB |
Output is correct |
15 |
Correct |
36 ms |
4252 KB |
Output is correct |
16 |
Correct |
29 ms |
5208 KB |
Output is correct |
17 |
Correct |
25 ms |
4696 KB |
Output is correct |
18 |
Correct |
881 ms |
5540 KB |
Output is correct |
19 |
Correct |
892 ms |
5516 KB |
Output is correct |
20 |
Correct |
864 ms |
5496 KB |
Output is correct |
21 |
Correct |
897 ms |
5640 KB |
Output is correct |
22 |
Correct |
880 ms |
5772 KB |
Output is correct |
23 |
Correct |
1061 ms |
8176 KB |
Output is correct |
24 |
Correct |
1033 ms |
8272 KB |
Output is correct |
25 |
Correct |
1029 ms |
8132 KB |
Output is correct |
26 |
Correct |
25 ms |
2900 KB |
Output is correct |
27 |
Correct |
549 ms |
6748 KB |
Output is correct |
28 |
Correct |
518 ms |
6440 KB |
Output is correct |
29 |
Correct |
716 ms |
4784 KB |
Output is correct |
30 |
Correct |
710 ms |
7976 KB |
Output is correct |
31 |
Correct |
644 ms |
5052 KB |
Output is correct |
32 |
Correct |
399 ms |
6152 KB |
Output is correct |
33 |
Correct |
686 ms |
6480 KB |
Output is correct |
34 |
Correct |
630 ms |
5036 KB |
Output is correct |
35 |
Correct |
25 ms |
2796 KB |
Output is correct |
36 |
Correct |
688 ms |
5384 KB |
Output is correct |
37 |
Correct |
608 ms |
5316 KB |
Output is correct |
38 |
Correct |
562 ms |
5072 KB |
Output is correct |
39 |
Correct |
470 ms |
4324 KB |
Output is correct |
40 |
Correct |
443 ms |
4292 KB |
Output is correct |
41 |
Correct |
481 ms |
7132 KB |
Output is correct |
42 |
Correct |
443 ms |
5920 KB |
Output is correct |
43 |
Correct |
1294 ms |
5440 KB |
Output is correct |
44 |
Correct |
31 ms |
4184 KB |
Output is correct |
45 |
Correct |
140 ms |
6740 KB |
Output is correct |
46 |
Correct |
60 ms |
6600 KB |
Output is correct |
47 |
Correct |
653 ms |
7812 KB |
Output is correct |
48 |
Correct |
1220 ms |
9392 KB |
Output is correct |
49 |
Correct |
602 ms |
7724 KB |
Output is correct |
50 |
Correct |
580 ms |
6744 KB |
Output is correct |
51 |
Correct |
569 ms |
6988 KB |
Output is correct |
52 |
Correct |
611 ms |
6672 KB |
Output is correct |
53 |
Correct |
920 ms |
8108 KB |
Output is correct |
54 |
Correct |
915 ms |
8252 KB |
Output is correct |
55 |
Correct |
928 ms |
8432 KB |
Output is correct |
56 |
Correct |
555 ms |
7660 KB |
Output is correct |
57 |
Correct |
575 ms |
7768 KB |
Output is correct |
58 |
Correct |
1397 ms |
9228 KB |
Output is correct |
59 |
Correct |
1281 ms |
9040 KB |
Output is correct |
60 |
Correct |
1251 ms |
9160 KB |
Output is correct |
61 |
Correct |
1295 ms |
9152 KB |
Output is correct |
62 |
Correct |
1044 ms |
8496 KB |
Output is correct |
63 |
Correct |
1042 ms |
8408 KB |
Output is correct |
64 |
Correct |
1206 ms |
9116 KB |
Output is correct |
65 |
Correct |
704 ms |
7200 KB |
Output is correct |
66 |
Correct |
874 ms |
5536 KB |
Output is correct |
67 |
Correct |
962 ms |
6716 KB |
Output is correct |
68 |
Correct |
946 ms |
5460 KB |
Output is correct |
69 |
Correct |
736 ms |
4888 KB |
Output is correct |
70 |
Correct |
958 ms |
6200 KB |
Output is correct |
71 |
Correct |
1000 ms |
6404 KB |
Output is correct |
72 |
Correct |
1008 ms |
6384 KB |
Output is correct |
73 |
Correct |
898 ms |
5480 KB |
Output is correct |
74 |
Correct |
896 ms |
5516 KB |
Output is correct |
75 |
Correct |
895 ms |
5468 KB |
Output is correct |
76 |
Correct |
746 ms |
4744 KB |
Output is correct |
77 |
Correct |
775 ms |
4688 KB |
Output is correct |
78 |
Correct |
728 ms |
4692 KB |
Output is correct |
79 |
Correct |
645 ms |
4252 KB |
Output is correct |
80 |
Correct |
641 ms |
4556 KB |
Output is correct |
81 |
Correct |
649 ms |
4212 KB |
Output is correct |
82 |
Correct |
625 ms |
5208 KB |
Output is correct |
83 |
Correct |
641 ms |
5296 KB |
Output is correct |
84 |
Correct |
626 ms |
5120 KB |
Output is correct |
85 |
Correct |
1521 ms |
10872 KB |
Output is correct |
86 |
Correct |
155 ms |
7972 KB |
Output is correct |
87 |
Correct |
80 ms |
9872 KB |
Output is correct |
88 |
Correct |
841 ms |
9504 KB |
Output is correct |
89 |
Correct |
1526 ms |
10344 KB |
Output is correct |
90 |
Correct |
828 ms |
9544 KB |
Output is correct |
91 |
Correct |
933 ms |
8360 KB |
Output is correct |
92 |
Correct |
939 ms |
8384 KB |
Output is correct |
93 |
Correct |
1078 ms |
9108 KB |
Output is correct |
94 |
Correct |
1284 ms |
9540 KB |
Output is correct |
95 |
Correct |
1245 ms |
9684 KB |
Output is correct |
96 |
Correct |
1256 ms |
11424 KB |
Output is correct |
97 |
Correct |
744 ms |
7920 KB |
Output is correct |
98 |
Correct |
730 ms |
10516 KB |
Output is correct |
99 |
Correct |
1567 ms |
10424 KB |
Output is correct |
100 |
Correct |
1586 ms |
10532 KB |
Output is correct |
101 |
Correct |
1627 ms |
10584 KB |
Output is correct |
102 |
Correct |
1552 ms |
10460 KB |
Output is correct |
103 |
Correct |
1444 ms |
11656 KB |
Output is correct |
104 |
Correct |
1392 ms |
11452 KB |
Output is correct |
105 |
Correct |
1230 ms |
12388 KB |
Output is correct |
106 |
Correct |
1002 ms |
11764 KB |
Output is correct |
107 |
Correct |
1202 ms |
8784 KB |
Output is correct |
108 |
Correct |
1486 ms |
10920 KB |
Output is correct |
109 |
Correct |
994 ms |
9424 KB |
Output is correct |