#include<bits/stdc++.h>
using namespace std;
const int B = 1000;
const int M = 1e5;
int sz[M + 1];
int par[M + 1];
stack<int> st;
void init(){
for(int i = 1; i <= M;i++){
sz[i] = 1;
par[i] = i;
}
}
int find(int a){
// if(par[a] == a){
// return a;
// }
// return par[a] = find(par[a]);
while(a != par[a]) a = par[a];
return a;
}
void join(int a,int b){
a = find(a);
b = find(b);
if(a == b) return;
if(sz[a] > sz[b]) swap(a,b);
sz[b] += sz[a];
par[a] = par[b];
st.push(a);
}
void rollback(int s){
while((int) st.size() > s){
int a = st.top();
st.pop();
sz[par[a]] -= sz[a];
par[a] = a;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin >> n >> m;
vector<array<int,3>> bridge(m + 1);
for(int i = 1;i <= m;i++){
cin >> bridge[i][0] >> bridge[i][1] >> bridge[i][2];
}
int q;
cin >> q;
vector<array<int,3>> query(q);
for(int i = 0;i < q;i++){
cin >> query[i][0] >> query[i][1] >> query[i][2];
}
vector<int> ans(q);
for(int i = 0;i < q;i += B){
init();
int l = i;
int r = min(q - 1,i + B);
vector<bool> isc(m + 1,false);
vector<int> upd,ask;
vector<vector<int>> tj(r - l + 1);
for(int j = l;j <= r;j ++){
if(query[j][0] == 1) upd.push_back(query[j][1]);
}
for(int j = l;j <= r;j ++){
if(query[j][0] == 1){
isc[query[j][1]] = true;
bridge[query[j][1]][2] = query[j][2];
}else{
for(int k : upd){
if(bridge[k][2] >= query[j][2]) tj[j - l].push_back(k);
}
ask.push_back(j);
}
}
vector<int> uc;
for(int j = 1;j <= m;j++){
if(!isc[j]){
uc.push_back(j);
}
}
sort(uc.begin(),uc.end(),[&](int &a,int &b){
return bridge[a][2] > bridge[b][2];
});
sort(ask.begin(),ask.end(),[&](int &a,int &b){
return query[a][2] > query[b][2];
});
int cur = 0;
for(int k : ask){
int w = query[k][2];
while(cur < (int) uc.size() && bridge[uc[cur]][2] >= w){
join(bridge[uc[cur]][0],bridge[uc[cur]][1]);
++ cur;
}
int ps = st.size();
for(int e : tj[k - l]){
join(bridge[e][0],bridge[e][1]);
}
int my = query[k][1];
ans[k] = sz[find(my)];
rollback(ps);
}
}
for(int i = 0;i < q;i++){
if(query[i][0] == 2) cout << ans[i] << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
27 ms |
2268 KB |
Output is correct |
4 |
Correct |
4 ms |
1368 KB |
Output is correct |
5 |
Correct |
27 ms |
2476 KB |
Output is correct |
6 |
Correct |
21 ms |
2452 KB |
Output is correct |
7 |
Correct |
23 ms |
2712 KB |
Output is correct |
8 |
Correct |
30 ms |
2184 KB |
Output is correct |
9 |
Correct |
29 ms |
3412 KB |
Output is correct |
10 |
Correct |
29 ms |
2140 KB |
Output is correct |
11 |
Correct |
29 ms |
2140 KB |
Output is correct |
12 |
Correct |
39 ms |
2396 KB |
Output is correct |
13 |
Correct |
34 ms |
2140 KB |
Output is correct |
14 |
Correct |
32 ms |
2140 KB |
Output is correct |
15 |
Correct |
36 ms |
2140 KB |
Output is correct |
16 |
Correct |
26 ms |
2908 KB |
Output is correct |
17 |
Correct |
27 ms |
2552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
879 ms |
24880 KB |
Output is correct |
2 |
Correct |
902 ms |
27224 KB |
Output is correct |
3 |
Correct |
879 ms |
27248 KB |
Output is correct |
4 |
Correct |
911 ms |
27772 KB |
Output is correct |
5 |
Correct |
904 ms |
27572 KB |
Output is correct |
6 |
Correct |
1026 ms |
28592 KB |
Output is correct |
7 |
Correct |
1054 ms |
28624 KB |
Output is correct |
8 |
Correct |
1044 ms |
27940 KB |
Output is correct |
9 |
Correct |
42 ms |
4444 KB |
Output is correct |
10 |
Correct |
542 ms |
27296 KB |
Output is correct |
11 |
Correct |
542 ms |
26896 KB |
Output is correct |
12 |
Correct |
747 ms |
27652 KB |
Output is correct |
13 |
Correct |
739 ms |
26740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
687 ms |
17364 KB |
Output is correct |
2 |
Correct |
420 ms |
9044 KB |
Output is correct |
3 |
Correct |
711 ms |
20200 KB |
Output is correct |
4 |
Correct |
678 ms |
19976 KB |
Output is correct |
5 |
Correct |
32 ms |
4208 KB |
Output is correct |
6 |
Correct |
711 ms |
20008 KB |
Output is correct |
7 |
Correct |
635 ms |
19896 KB |
Output is correct |
8 |
Correct |
576 ms |
19192 KB |
Output is correct |
9 |
Correct |
481 ms |
19708 KB |
Output is correct |
10 |
Correct |
474 ms |
19644 KB |
Output is correct |
11 |
Correct |
498 ms |
18840 KB |
Output is correct |
12 |
Correct |
460 ms |
18688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1264 ms |
25236 KB |
Output is correct |
2 |
Correct |
33 ms |
4188 KB |
Output is correct |
3 |
Correct |
135 ms |
5372 KB |
Output is correct |
4 |
Correct |
61 ms |
5444 KB |
Output is correct |
5 |
Correct |
615 ms |
27756 KB |
Output is correct |
6 |
Correct |
1218 ms |
29288 KB |
Output is correct |
7 |
Correct |
601 ms |
27636 KB |
Output is correct |
8 |
Correct |
588 ms |
26968 KB |
Output is correct |
9 |
Correct |
569 ms |
27232 KB |
Output is correct |
10 |
Correct |
579 ms |
27180 KB |
Output is correct |
11 |
Correct |
929 ms |
28476 KB |
Output is correct |
12 |
Correct |
909 ms |
28492 KB |
Output is correct |
13 |
Correct |
941 ms |
28616 KB |
Output is correct |
14 |
Correct |
541 ms |
27836 KB |
Output is correct |
15 |
Correct |
573 ms |
27672 KB |
Output is correct |
16 |
Correct |
1266 ms |
29336 KB |
Output is correct |
17 |
Correct |
1270 ms |
29232 KB |
Output is correct |
18 |
Correct |
1260 ms |
29472 KB |
Output is correct |
19 |
Correct |
1248 ms |
29716 KB |
Output is correct |
20 |
Correct |
1058 ms |
28880 KB |
Output is correct |
21 |
Correct |
1060 ms |
28772 KB |
Output is correct |
22 |
Correct |
1209 ms |
28668 KB |
Output is correct |
23 |
Correct |
689 ms |
25404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
879 ms |
24880 KB |
Output is correct |
2 |
Correct |
902 ms |
27224 KB |
Output is correct |
3 |
Correct |
879 ms |
27248 KB |
Output is correct |
4 |
Correct |
911 ms |
27772 KB |
Output is correct |
5 |
Correct |
904 ms |
27572 KB |
Output is correct |
6 |
Correct |
1026 ms |
28592 KB |
Output is correct |
7 |
Correct |
1054 ms |
28624 KB |
Output is correct |
8 |
Correct |
1044 ms |
27940 KB |
Output is correct |
9 |
Correct |
42 ms |
4444 KB |
Output is correct |
10 |
Correct |
542 ms |
27296 KB |
Output is correct |
11 |
Correct |
542 ms |
26896 KB |
Output is correct |
12 |
Correct |
747 ms |
27652 KB |
Output is correct |
13 |
Correct |
739 ms |
26740 KB |
Output is correct |
14 |
Correct |
687 ms |
17364 KB |
Output is correct |
15 |
Correct |
420 ms |
9044 KB |
Output is correct |
16 |
Correct |
711 ms |
20200 KB |
Output is correct |
17 |
Correct |
678 ms |
19976 KB |
Output is correct |
18 |
Correct |
32 ms |
4208 KB |
Output is correct |
19 |
Correct |
711 ms |
20008 KB |
Output is correct |
20 |
Correct |
635 ms |
19896 KB |
Output is correct |
21 |
Correct |
576 ms |
19192 KB |
Output is correct |
22 |
Correct |
481 ms |
19708 KB |
Output is correct |
23 |
Correct |
474 ms |
19644 KB |
Output is correct |
24 |
Correct |
498 ms |
18840 KB |
Output is correct |
25 |
Correct |
460 ms |
18688 KB |
Output is correct |
26 |
Correct |
936 ms |
27568 KB |
Output is correct |
27 |
Correct |
989 ms |
27648 KB |
Output is correct |
28 |
Correct |
920 ms |
27480 KB |
Output is correct |
29 |
Correct |
736 ms |
26940 KB |
Output is correct |
30 |
Correct |
983 ms |
27608 KB |
Output is correct |
31 |
Correct |
989 ms |
27528 KB |
Output is correct |
32 |
Correct |
996 ms |
27552 KB |
Output is correct |
33 |
Correct |
897 ms |
27396 KB |
Output is correct |
34 |
Correct |
923 ms |
27460 KB |
Output is correct |
35 |
Correct |
923 ms |
27704 KB |
Output is correct |
36 |
Correct |
772 ms |
26796 KB |
Output is correct |
37 |
Correct |
760 ms |
26924 KB |
Output is correct |
38 |
Correct |
751 ms |
26836 KB |
Output is correct |
39 |
Correct |
656 ms |
27088 KB |
Output is correct |
40 |
Correct |
659 ms |
27092 KB |
Output is correct |
41 |
Correct |
648 ms |
27044 KB |
Output is correct |
42 |
Correct |
642 ms |
26064 KB |
Output is correct |
43 |
Correct |
632 ms |
25912 KB |
Output is correct |
44 |
Correct |
637 ms |
25880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
27 ms |
2268 KB |
Output is correct |
4 |
Correct |
4 ms |
1368 KB |
Output is correct |
5 |
Correct |
27 ms |
2476 KB |
Output is correct |
6 |
Correct |
21 ms |
2452 KB |
Output is correct |
7 |
Correct |
23 ms |
2712 KB |
Output is correct |
8 |
Correct |
30 ms |
2184 KB |
Output is correct |
9 |
Correct |
29 ms |
3412 KB |
Output is correct |
10 |
Correct |
29 ms |
2140 KB |
Output is correct |
11 |
Correct |
29 ms |
2140 KB |
Output is correct |
12 |
Correct |
39 ms |
2396 KB |
Output is correct |
13 |
Correct |
34 ms |
2140 KB |
Output is correct |
14 |
Correct |
32 ms |
2140 KB |
Output is correct |
15 |
Correct |
36 ms |
2140 KB |
Output is correct |
16 |
Correct |
26 ms |
2908 KB |
Output is correct |
17 |
Correct |
27 ms |
2552 KB |
Output is correct |
18 |
Correct |
879 ms |
24880 KB |
Output is correct |
19 |
Correct |
902 ms |
27224 KB |
Output is correct |
20 |
Correct |
879 ms |
27248 KB |
Output is correct |
21 |
Correct |
911 ms |
27772 KB |
Output is correct |
22 |
Correct |
904 ms |
27572 KB |
Output is correct |
23 |
Correct |
1026 ms |
28592 KB |
Output is correct |
24 |
Correct |
1054 ms |
28624 KB |
Output is correct |
25 |
Correct |
1044 ms |
27940 KB |
Output is correct |
26 |
Correct |
42 ms |
4444 KB |
Output is correct |
27 |
Correct |
542 ms |
27296 KB |
Output is correct |
28 |
Correct |
542 ms |
26896 KB |
Output is correct |
29 |
Correct |
747 ms |
27652 KB |
Output is correct |
30 |
Correct |
739 ms |
26740 KB |
Output is correct |
31 |
Correct |
687 ms |
17364 KB |
Output is correct |
32 |
Correct |
420 ms |
9044 KB |
Output is correct |
33 |
Correct |
711 ms |
20200 KB |
Output is correct |
34 |
Correct |
678 ms |
19976 KB |
Output is correct |
35 |
Correct |
32 ms |
4208 KB |
Output is correct |
36 |
Correct |
711 ms |
20008 KB |
Output is correct |
37 |
Correct |
635 ms |
19896 KB |
Output is correct |
38 |
Correct |
576 ms |
19192 KB |
Output is correct |
39 |
Correct |
481 ms |
19708 KB |
Output is correct |
40 |
Correct |
474 ms |
19644 KB |
Output is correct |
41 |
Correct |
498 ms |
18840 KB |
Output is correct |
42 |
Correct |
460 ms |
18688 KB |
Output is correct |
43 |
Correct |
1264 ms |
25236 KB |
Output is correct |
44 |
Correct |
33 ms |
4188 KB |
Output is correct |
45 |
Correct |
135 ms |
5372 KB |
Output is correct |
46 |
Correct |
61 ms |
5444 KB |
Output is correct |
47 |
Correct |
615 ms |
27756 KB |
Output is correct |
48 |
Correct |
1218 ms |
29288 KB |
Output is correct |
49 |
Correct |
601 ms |
27636 KB |
Output is correct |
50 |
Correct |
588 ms |
26968 KB |
Output is correct |
51 |
Correct |
569 ms |
27232 KB |
Output is correct |
52 |
Correct |
579 ms |
27180 KB |
Output is correct |
53 |
Correct |
929 ms |
28476 KB |
Output is correct |
54 |
Correct |
909 ms |
28492 KB |
Output is correct |
55 |
Correct |
941 ms |
28616 KB |
Output is correct |
56 |
Correct |
541 ms |
27836 KB |
Output is correct |
57 |
Correct |
573 ms |
27672 KB |
Output is correct |
58 |
Correct |
1266 ms |
29336 KB |
Output is correct |
59 |
Correct |
1270 ms |
29232 KB |
Output is correct |
60 |
Correct |
1260 ms |
29472 KB |
Output is correct |
61 |
Correct |
1248 ms |
29716 KB |
Output is correct |
62 |
Correct |
1058 ms |
28880 KB |
Output is correct |
63 |
Correct |
1060 ms |
28772 KB |
Output is correct |
64 |
Correct |
1209 ms |
28668 KB |
Output is correct |
65 |
Correct |
689 ms |
25404 KB |
Output is correct |
66 |
Correct |
936 ms |
27568 KB |
Output is correct |
67 |
Correct |
989 ms |
27648 KB |
Output is correct |
68 |
Correct |
920 ms |
27480 KB |
Output is correct |
69 |
Correct |
736 ms |
26940 KB |
Output is correct |
70 |
Correct |
983 ms |
27608 KB |
Output is correct |
71 |
Correct |
989 ms |
27528 KB |
Output is correct |
72 |
Correct |
996 ms |
27552 KB |
Output is correct |
73 |
Correct |
897 ms |
27396 KB |
Output is correct |
74 |
Correct |
923 ms |
27460 KB |
Output is correct |
75 |
Correct |
923 ms |
27704 KB |
Output is correct |
76 |
Correct |
772 ms |
26796 KB |
Output is correct |
77 |
Correct |
760 ms |
26924 KB |
Output is correct |
78 |
Correct |
751 ms |
26836 KB |
Output is correct |
79 |
Correct |
656 ms |
27088 KB |
Output is correct |
80 |
Correct |
659 ms |
27092 KB |
Output is correct |
81 |
Correct |
648 ms |
27044 KB |
Output is correct |
82 |
Correct |
642 ms |
26064 KB |
Output is correct |
83 |
Correct |
632 ms |
25912 KB |
Output is correct |
84 |
Correct |
637 ms |
25880 KB |
Output is correct |
85 |
Correct |
1530 ms |
29584 KB |
Output is correct |
86 |
Correct |
156 ms |
5892 KB |
Output is correct |
87 |
Correct |
89 ms |
7276 KB |
Output is correct |
88 |
Correct |
853 ms |
28488 KB |
Output is correct |
89 |
Correct |
1553 ms |
29492 KB |
Output is correct |
90 |
Correct |
877 ms |
28268 KB |
Output is correct |
91 |
Correct |
983 ms |
27380 KB |
Output is correct |
92 |
Correct |
961 ms |
27420 KB |
Output is correct |
93 |
Correct |
1135 ms |
27672 KB |
Output is correct |
94 |
Correct |
1294 ms |
28776 KB |
Output is correct |
95 |
Correct |
1276 ms |
28908 KB |
Output is correct |
96 |
Correct |
1306 ms |
29292 KB |
Output is correct |
97 |
Correct |
742 ms |
27820 KB |
Output is correct |
98 |
Correct |
727 ms |
27388 KB |
Output is correct |
99 |
Correct |
1609 ms |
29800 KB |
Output is correct |
100 |
Correct |
1581 ms |
29612 KB |
Output is correct |
101 |
Correct |
1615 ms |
29936 KB |
Output is correct |
102 |
Correct |
1593 ms |
29808 KB |
Output is correct |
103 |
Correct |
1424 ms |
30360 KB |
Output is correct |
104 |
Correct |
1455 ms |
30292 KB |
Output is correct |
105 |
Correct |
1225 ms |
29032 KB |
Output is correct |
106 |
Correct |
1032 ms |
28164 KB |
Output is correct |
107 |
Correct |
1188 ms |
28932 KB |
Output is correct |
108 |
Correct |
1519 ms |
29756 KB |
Output is correct |
109 |
Correct |
972 ms |
26068 KB |
Output is correct |