#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+10,maxm=100000+10,sq=1500;
int n,m,q,res[maxm];
struct yal{
int u,v,w,tagh,asl;
}alle[maxm];
struct qu{
int qq,ind,w;
}allq[maxm];
struct dsu{
vector<int>allv;
int par[maxn],sz[maxn];
dsu(){
for(int i=1;i<maxn;i++){
par[i]=i;
sz[i]=1;
}
}
void clear(){
allv.clear();
for(int i=1;i<maxn;i++){
par[i]=i;
sz[i]=1;
}
}
int root(int u){
if(u==par[u]){
return u;
}
return root(par[u]);
}
void con(int u,int v){
int rootu=root(u),rootv=root(v);
if(rootu!=rootv){
if(sz[rootu]<sz[rootv]){
swap(rootu,rootv);
}
allv.push_back(rootv);
par[rootv]=rootu;
sz[rootu]+=sz[rootv];
return ;
}
allv.push_back(-1);
}
int gets(int u){
return sz[root(u)];
}
void back(){
int x=allv.back();
allv.pop_back();
if(x==-1){
return ;
}
sz[par[x]]-=sz[x];
par[x]=x;
}
}ds;
vector<int>allp,allind,allval,que[maxm];
bool cmp(int a,int b){
if(alle[a].w!=alle[b].w){
return alle[a].w<alle[b].w;
}
if(alle[a].u!=alle[b].w){
return alle[a].u<alle[b].u;
}
return alle[a].v<alle[b].v;
}
void vorod(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>alle[i].u>>alle[i].v>>alle[i].w;
alle[i].w*=-1;
alle[i].tagh=0;
alle[i].asl=alle[i].w;
allind.push_back(i);
}
sort(allind.begin(),allind.end(),cmp);
for(auto x:allind){
allval.push_back(alle[x].w);
}
cin>>q;
for(int i=0;i<q;i++){
cin>>allq[i].qq>>allq[i].ind>>allq[i].w;
allq[i].w*=-1;
}
}
void calq(int ind){
for(auto x:que[ind]){
int l=x-(x%sq);
for(int i=l;i<x;i++){
if(allq[i].qq==1){
alle[allq[i].ind].w=allq[i].w;
}
}
for(auto y:allp){
if(allq[x].w>=alle[y].w){
ds.con(alle[y].u,alle[y].v);
}
}
res[x]=ds.gets(allq[x].ind);
for(auto y:allp){
if(allq[x].w>=alle[y].w){
ds.back();
}
}
for(int i=l;i<x;i++){
if(allq[i].qq==1){
alle[allq[i].ind].w=alle[allq[i].ind].asl;
}
}
}
que[ind].clear();
}
void solve(){
for(int l=0;l<q;l+=sq){
sort(allind.begin(),allind.end(),cmp);
allval.clear();
for(auto x:allind){
allval.push_back(alle[x].w);
}
ds.clear();
allp.clear();
for(int i=l;i<min(q,l+sq);i++){
if(allq[i].qq==1){
alle[allq[i].ind].tagh=1;
allp.push_back(allq[i].ind);
}
else{
int p=upper_bound(allval.begin(),allval.end(),allq[i].w)-allval.begin();
que[p].push_back(i);
}
}
for(int i=0;i<(int)allind.size();i++){
calq(i);
if(alle[allind[i]].tagh==0){
ds.con(alle[allind[i]].u,alle[allind[i]].v);
}
}
calq((int)allind.size());
for(int i=l;i<min(q,l+sq);i++){
if(allq[i].qq==1){
alle[allq[i].ind].tagh=0;
alle[allq[i].ind].w=alle[allq[i].ind].asl=allq[i].w;
}
}
}
}
void khor(){
for(int i=0;i<q;i++){
if(allq[i].qq==2)
cout<<res[i]<<"\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
vorod();
solve();
khor();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4700 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
59 ms |
4796 KB |
Output is correct |
4 |
Correct |
27 ms |
4696 KB |
Output is correct |
5 |
Correct |
50 ms |
4772 KB |
Output is correct |
6 |
Correct |
39 ms |
4700 KB |
Output is correct |
7 |
Correct |
37 ms |
4696 KB |
Output is correct |
8 |
Correct |
57 ms |
4776 KB |
Output is correct |
9 |
Correct |
37 ms |
4700 KB |
Output is correct |
10 |
Correct |
61 ms |
4776 KB |
Output is correct |
11 |
Correct |
58 ms |
4780 KB |
Output is correct |
12 |
Correct |
68 ms |
4780 KB |
Output is correct |
13 |
Correct |
64 ms |
4784 KB |
Output is correct |
14 |
Correct |
74 ms |
4784 KB |
Output is correct |
15 |
Correct |
70 ms |
4760 KB |
Output is correct |
16 |
Correct |
47 ms |
4776 KB |
Output is correct |
17 |
Correct |
45 ms |
4696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
909 ms |
7228 KB |
Output is correct |
2 |
Correct |
884 ms |
7312 KB |
Output is correct |
3 |
Correct |
908 ms |
7384 KB |
Output is correct |
4 |
Correct |
1047 ms |
7288 KB |
Output is correct |
5 |
Correct |
943 ms |
7292 KB |
Output is correct |
6 |
Correct |
1107 ms |
6752 KB |
Output is correct |
7 |
Correct |
1118 ms |
6828 KB |
Output is correct |
8 |
Correct |
1156 ms |
6812 KB |
Output is correct |
9 |
Correct |
143 ms |
5200 KB |
Output is correct |
10 |
Correct |
830 ms |
6796 KB |
Output is correct |
11 |
Correct |
928 ms |
6780 KB |
Output is correct |
12 |
Correct |
899 ms |
7032 KB |
Output is correct |
13 |
Correct |
628 ms |
6484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
711 ms |
6524 KB |
Output is correct |
2 |
Correct |
550 ms |
5432 KB |
Output is correct |
3 |
Correct |
726 ms |
6528 KB |
Output is correct |
4 |
Correct |
687 ms |
6528 KB |
Output is correct |
5 |
Correct |
150 ms |
5112 KB |
Output is correct |
6 |
Correct |
741 ms |
6552 KB |
Output is correct |
7 |
Correct |
892 ms |
6616 KB |
Output is correct |
8 |
Correct |
628 ms |
6576 KB |
Output is correct |
9 |
Correct |
554 ms |
6700 KB |
Output is correct |
10 |
Correct |
538 ms |
6760 KB |
Output is correct |
11 |
Correct |
457 ms |
5908 KB |
Output is correct |
12 |
Correct |
408 ms |
6304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
919 ms |
9864 KB |
Output is correct |
2 |
Correct |
245 ms |
5088 KB |
Output is correct |
3 |
Correct |
111 ms |
7792 KB |
Output is correct |
4 |
Correct |
84 ms |
7760 KB |
Output is correct |
5 |
Correct |
1084 ms |
8460 KB |
Output is correct |
6 |
Correct |
907 ms |
9840 KB |
Output is correct |
7 |
Correct |
877 ms |
8476 KB |
Output is correct |
8 |
Correct |
472 ms |
7544 KB |
Output is correct |
9 |
Correct |
465 ms |
7352 KB |
Output is correct |
10 |
Correct |
487 ms |
6936 KB |
Output is correct |
11 |
Correct |
683 ms |
8872 KB |
Output is correct |
12 |
Correct |
670 ms |
8656 KB |
Output is correct |
13 |
Correct |
877 ms |
7524 KB |
Output is correct |
14 |
Correct |
1040 ms |
8512 KB |
Output is correct |
15 |
Correct |
829 ms |
8404 KB |
Output is correct |
16 |
Correct |
948 ms |
10176 KB |
Output is correct |
17 |
Correct |
903 ms |
9692 KB |
Output is correct |
18 |
Correct |
870 ms |
9684 KB |
Output is correct |
19 |
Correct |
881 ms |
9860 KB |
Output is correct |
20 |
Correct |
922 ms |
8060 KB |
Output is correct |
21 |
Correct |
854 ms |
8016 KB |
Output is correct |
22 |
Correct |
871 ms |
8932 KB |
Output is correct |
23 |
Correct |
684 ms |
7956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
909 ms |
7228 KB |
Output is correct |
2 |
Correct |
884 ms |
7312 KB |
Output is correct |
3 |
Correct |
908 ms |
7384 KB |
Output is correct |
4 |
Correct |
1047 ms |
7288 KB |
Output is correct |
5 |
Correct |
943 ms |
7292 KB |
Output is correct |
6 |
Correct |
1107 ms |
6752 KB |
Output is correct |
7 |
Correct |
1118 ms |
6828 KB |
Output is correct |
8 |
Correct |
1156 ms |
6812 KB |
Output is correct |
9 |
Correct |
143 ms |
5200 KB |
Output is correct |
10 |
Correct |
830 ms |
6796 KB |
Output is correct |
11 |
Correct |
928 ms |
6780 KB |
Output is correct |
12 |
Correct |
899 ms |
7032 KB |
Output is correct |
13 |
Correct |
628 ms |
6484 KB |
Output is correct |
14 |
Correct |
711 ms |
6524 KB |
Output is correct |
15 |
Correct |
550 ms |
5432 KB |
Output is correct |
16 |
Correct |
726 ms |
6528 KB |
Output is correct |
17 |
Correct |
687 ms |
6528 KB |
Output is correct |
18 |
Correct |
150 ms |
5112 KB |
Output is correct |
19 |
Correct |
741 ms |
6552 KB |
Output is correct |
20 |
Correct |
892 ms |
6616 KB |
Output is correct |
21 |
Correct |
628 ms |
6576 KB |
Output is correct |
22 |
Correct |
554 ms |
6700 KB |
Output is correct |
23 |
Correct |
538 ms |
6760 KB |
Output is correct |
24 |
Correct |
457 ms |
5908 KB |
Output is correct |
25 |
Correct |
408 ms |
6304 KB |
Output is correct |
26 |
Correct |
950 ms |
7380 KB |
Output is correct |
27 |
Correct |
952 ms |
6948 KB |
Output is correct |
28 |
Correct |
930 ms |
7324 KB |
Output is correct |
29 |
Correct |
755 ms |
6888 KB |
Output is correct |
30 |
Correct |
1018 ms |
7288 KB |
Output is correct |
31 |
Correct |
963 ms |
7056 KB |
Output is correct |
32 |
Correct |
1020 ms |
7528 KB |
Output is correct |
33 |
Correct |
922 ms |
7624 KB |
Output is correct |
34 |
Correct |
893 ms |
7244 KB |
Output is correct |
35 |
Correct |
883 ms |
7248 KB |
Output is correct |
36 |
Correct |
754 ms |
7068 KB |
Output is correct |
37 |
Correct |
734 ms |
6912 KB |
Output is correct |
38 |
Correct |
726 ms |
6892 KB |
Output is correct |
39 |
Correct |
677 ms |
7288 KB |
Output is correct |
40 |
Correct |
791 ms |
7232 KB |
Output is correct |
41 |
Correct |
668 ms |
7336 KB |
Output is correct |
42 |
Correct |
577 ms |
6592 KB |
Output is correct |
43 |
Correct |
495 ms |
6484 KB |
Output is correct |
44 |
Correct |
498 ms |
6484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4700 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
59 ms |
4796 KB |
Output is correct |
4 |
Correct |
27 ms |
4696 KB |
Output is correct |
5 |
Correct |
50 ms |
4772 KB |
Output is correct |
6 |
Correct |
39 ms |
4700 KB |
Output is correct |
7 |
Correct |
37 ms |
4696 KB |
Output is correct |
8 |
Correct |
57 ms |
4776 KB |
Output is correct |
9 |
Correct |
37 ms |
4700 KB |
Output is correct |
10 |
Correct |
61 ms |
4776 KB |
Output is correct |
11 |
Correct |
58 ms |
4780 KB |
Output is correct |
12 |
Correct |
68 ms |
4780 KB |
Output is correct |
13 |
Correct |
64 ms |
4784 KB |
Output is correct |
14 |
Correct |
74 ms |
4784 KB |
Output is correct |
15 |
Correct |
70 ms |
4760 KB |
Output is correct |
16 |
Correct |
47 ms |
4776 KB |
Output is correct |
17 |
Correct |
45 ms |
4696 KB |
Output is correct |
18 |
Correct |
909 ms |
7228 KB |
Output is correct |
19 |
Correct |
884 ms |
7312 KB |
Output is correct |
20 |
Correct |
908 ms |
7384 KB |
Output is correct |
21 |
Correct |
1047 ms |
7288 KB |
Output is correct |
22 |
Correct |
943 ms |
7292 KB |
Output is correct |
23 |
Correct |
1107 ms |
6752 KB |
Output is correct |
24 |
Correct |
1118 ms |
6828 KB |
Output is correct |
25 |
Correct |
1156 ms |
6812 KB |
Output is correct |
26 |
Correct |
143 ms |
5200 KB |
Output is correct |
27 |
Correct |
830 ms |
6796 KB |
Output is correct |
28 |
Correct |
928 ms |
6780 KB |
Output is correct |
29 |
Correct |
899 ms |
7032 KB |
Output is correct |
30 |
Correct |
628 ms |
6484 KB |
Output is correct |
31 |
Correct |
711 ms |
6524 KB |
Output is correct |
32 |
Correct |
550 ms |
5432 KB |
Output is correct |
33 |
Correct |
726 ms |
6528 KB |
Output is correct |
34 |
Correct |
687 ms |
6528 KB |
Output is correct |
35 |
Correct |
150 ms |
5112 KB |
Output is correct |
36 |
Correct |
741 ms |
6552 KB |
Output is correct |
37 |
Correct |
892 ms |
6616 KB |
Output is correct |
38 |
Correct |
628 ms |
6576 KB |
Output is correct |
39 |
Correct |
554 ms |
6700 KB |
Output is correct |
40 |
Correct |
538 ms |
6760 KB |
Output is correct |
41 |
Correct |
457 ms |
5908 KB |
Output is correct |
42 |
Correct |
408 ms |
6304 KB |
Output is correct |
43 |
Correct |
919 ms |
9864 KB |
Output is correct |
44 |
Correct |
245 ms |
5088 KB |
Output is correct |
45 |
Correct |
111 ms |
7792 KB |
Output is correct |
46 |
Correct |
84 ms |
7760 KB |
Output is correct |
47 |
Correct |
1084 ms |
8460 KB |
Output is correct |
48 |
Correct |
907 ms |
9840 KB |
Output is correct |
49 |
Correct |
877 ms |
8476 KB |
Output is correct |
50 |
Correct |
472 ms |
7544 KB |
Output is correct |
51 |
Correct |
465 ms |
7352 KB |
Output is correct |
52 |
Correct |
487 ms |
6936 KB |
Output is correct |
53 |
Correct |
683 ms |
8872 KB |
Output is correct |
54 |
Correct |
670 ms |
8656 KB |
Output is correct |
55 |
Correct |
877 ms |
7524 KB |
Output is correct |
56 |
Correct |
1040 ms |
8512 KB |
Output is correct |
57 |
Correct |
829 ms |
8404 KB |
Output is correct |
58 |
Correct |
948 ms |
10176 KB |
Output is correct |
59 |
Correct |
903 ms |
9692 KB |
Output is correct |
60 |
Correct |
870 ms |
9684 KB |
Output is correct |
61 |
Correct |
881 ms |
9860 KB |
Output is correct |
62 |
Correct |
922 ms |
8060 KB |
Output is correct |
63 |
Correct |
854 ms |
8016 KB |
Output is correct |
64 |
Correct |
871 ms |
8932 KB |
Output is correct |
65 |
Correct |
684 ms |
7956 KB |
Output is correct |
66 |
Correct |
950 ms |
7380 KB |
Output is correct |
67 |
Correct |
952 ms |
6948 KB |
Output is correct |
68 |
Correct |
930 ms |
7324 KB |
Output is correct |
69 |
Correct |
755 ms |
6888 KB |
Output is correct |
70 |
Correct |
1018 ms |
7288 KB |
Output is correct |
71 |
Correct |
963 ms |
7056 KB |
Output is correct |
72 |
Correct |
1020 ms |
7528 KB |
Output is correct |
73 |
Correct |
922 ms |
7624 KB |
Output is correct |
74 |
Correct |
893 ms |
7244 KB |
Output is correct |
75 |
Correct |
883 ms |
7248 KB |
Output is correct |
76 |
Correct |
754 ms |
7068 KB |
Output is correct |
77 |
Correct |
734 ms |
6912 KB |
Output is correct |
78 |
Correct |
726 ms |
6892 KB |
Output is correct |
79 |
Correct |
677 ms |
7288 KB |
Output is correct |
80 |
Correct |
791 ms |
7232 KB |
Output is correct |
81 |
Correct |
668 ms |
7336 KB |
Output is correct |
82 |
Correct |
577 ms |
6592 KB |
Output is correct |
83 |
Correct |
495 ms |
6484 KB |
Output is correct |
84 |
Correct |
498 ms |
6484 KB |
Output is correct |
85 |
Correct |
1655 ms |
9220 KB |
Output is correct |
86 |
Correct |
160 ms |
7864 KB |
Output is correct |
87 |
Correct |
102 ms |
7776 KB |
Output is correct |
88 |
Correct |
1587 ms |
8204 KB |
Output is correct |
89 |
Correct |
1628 ms |
9280 KB |
Output is correct |
90 |
Correct |
1411 ms |
8320 KB |
Output is correct |
91 |
Correct |
917 ms |
7276 KB |
Output is correct |
92 |
Correct |
1026 ms |
7316 KB |
Output is correct |
93 |
Correct |
1299 ms |
6836 KB |
Output is correct |
94 |
Correct |
1642 ms |
8532 KB |
Output is correct |
95 |
Correct |
1355 ms |
8304 KB |
Output is correct |
96 |
Correct |
1402 ms |
7420 KB |
Output is correct |
97 |
Correct |
1411 ms |
8408 KB |
Output is correct |
98 |
Correct |
1111 ms |
8152 KB |
Output is correct |
99 |
Correct |
1622 ms |
9504 KB |
Output is correct |
100 |
Correct |
1572 ms |
9148 KB |
Output is correct |
101 |
Correct |
1628 ms |
9076 KB |
Output is correct |
102 |
Correct |
1519 ms |
9280 KB |
Output is correct |
103 |
Correct |
1338 ms |
7852 KB |
Output is correct |
104 |
Correct |
1365 ms |
7976 KB |
Output is correct |
105 |
Correct |
954 ms |
7828 KB |
Output is correct |
106 |
Correct |
758 ms |
7308 KB |
Output is correct |
107 |
Correct |
1108 ms |
7988 KB |
Output is correct |
108 |
Correct |
1474 ms |
9152 KB |
Output is correct |
109 |
Correct |
1208 ms |
7596 KB |
Output is correct |