#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+10,maxm=100000+10,sq=600;
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();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
2 ms |
4700 KB |
Output is correct |
3 |
Correct |
21 ms |
4696 KB |
Output is correct |
4 |
Correct |
8 ms |
4952 KB |
Output is correct |
5 |
Correct |
22 ms |
4700 KB |
Output is correct |
6 |
Correct |
17 ms |
4696 KB |
Output is correct |
7 |
Correct |
18 ms |
4788 KB |
Output is correct |
8 |
Correct |
25 ms |
4700 KB |
Output is correct |
9 |
Correct |
16 ms |
4700 KB |
Output is correct |
10 |
Correct |
28 ms |
4700 KB |
Output is correct |
11 |
Correct |
26 ms |
4700 KB |
Output is correct |
12 |
Correct |
27 ms |
4696 KB |
Output is correct |
13 |
Correct |
34 ms |
4792 KB |
Output is correct |
14 |
Correct |
25 ms |
4700 KB |
Output is correct |
15 |
Correct |
35 ms |
4700 KB |
Output is correct |
16 |
Correct |
26 ms |
4696 KB |
Output is correct |
17 |
Correct |
26 ms |
4696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1237 ms |
7496 KB |
Output is correct |
2 |
Correct |
1224 ms |
7292 KB |
Output is correct |
3 |
Correct |
1187 ms |
7400 KB |
Output is correct |
4 |
Correct |
1234 ms |
7372 KB |
Output is correct |
5 |
Correct |
1269 ms |
7508 KB |
Output is correct |
6 |
Correct |
1258 ms |
6948 KB |
Output is correct |
7 |
Correct |
1296 ms |
6796 KB |
Output is correct |
8 |
Correct |
1851 ms |
6612 KB |
Output is correct |
9 |
Correct |
73 ms |
5232 KB |
Output is correct |
10 |
Correct |
1134 ms |
6652 KB |
Output is correct |
11 |
Correct |
1073 ms |
6920 KB |
Output is correct |
12 |
Correct |
1146 ms |
6988 KB |
Output is correct |
13 |
Correct |
1044 ms |
6740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
780 ms |
6544 KB |
Output is correct |
2 |
Correct |
388 ms |
5456 KB |
Output is correct |
3 |
Correct |
787 ms |
6708 KB |
Output is correct |
4 |
Correct |
803 ms |
6752 KB |
Output is correct |
5 |
Correct |
77 ms |
5200 KB |
Output is correct |
6 |
Correct |
812 ms |
6740 KB |
Output is correct |
7 |
Correct |
784 ms |
6560 KB |
Output is correct |
8 |
Correct |
765 ms |
6804 KB |
Output is correct |
9 |
Correct |
748 ms |
6736 KB |
Output is correct |
10 |
Correct |
1034 ms |
7084 KB |
Output is correct |
11 |
Correct |
637 ms |
5972 KB |
Output is correct |
12 |
Correct |
625 ms |
5968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1785 ms |
10008 KB |
Output is correct |
2 |
Correct |
73 ms |
5204 KB |
Output is correct |
3 |
Correct |
203 ms |
7752 KB |
Output is correct |
4 |
Correct |
135 ms |
7768 KB |
Output is correct |
5 |
Correct |
1746 ms |
8524 KB |
Output is correct |
6 |
Correct |
1813 ms |
9664 KB |
Output is correct |
7 |
Correct |
1813 ms |
8444 KB |
Output is correct |
8 |
Correct |
868 ms |
7552 KB |
Output is correct |
9 |
Correct |
855 ms |
7464 KB |
Output is correct |
10 |
Correct |
816 ms |
6908 KB |
Output is correct |
11 |
Correct |
1296 ms |
8520 KB |
Output is correct |
12 |
Correct |
1328 ms |
8748 KB |
Output is correct |
13 |
Correct |
1371 ms |
7720 KB |
Output is correct |
14 |
Correct |
1770 ms |
8380 KB |
Output is correct |
15 |
Correct |
1745 ms |
8512 KB |
Output is correct |
16 |
Correct |
1876 ms |
9764 KB |
Output is correct |
17 |
Correct |
1845 ms |
9760 KB |
Output is correct |
18 |
Correct |
1876 ms |
9680 KB |
Output is correct |
19 |
Correct |
1816 ms |
9680 KB |
Output is correct |
20 |
Correct |
1573 ms |
8280 KB |
Output is correct |
21 |
Correct |
1557 ms |
7964 KB |
Output is correct |
22 |
Correct |
1804 ms |
9240 KB |
Output is correct |
23 |
Correct |
1394 ms |
8096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1237 ms |
7496 KB |
Output is correct |
2 |
Correct |
1224 ms |
7292 KB |
Output is correct |
3 |
Correct |
1187 ms |
7400 KB |
Output is correct |
4 |
Correct |
1234 ms |
7372 KB |
Output is correct |
5 |
Correct |
1269 ms |
7508 KB |
Output is correct |
6 |
Correct |
1258 ms |
6948 KB |
Output is correct |
7 |
Correct |
1296 ms |
6796 KB |
Output is correct |
8 |
Correct |
1851 ms |
6612 KB |
Output is correct |
9 |
Correct |
73 ms |
5232 KB |
Output is correct |
10 |
Correct |
1134 ms |
6652 KB |
Output is correct |
11 |
Correct |
1073 ms |
6920 KB |
Output is correct |
12 |
Correct |
1146 ms |
6988 KB |
Output is correct |
13 |
Correct |
1044 ms |
6740 KB |
Output is correct |
14 |
Correct |
780 ms |
6544 KB |
Output is correct |
15 |
Correct |
388 ms |
5456 KB |
Output is correct |
16 |
Correct |
787 ms |
6708 KB |
Output is correct |
17 |
Correct |
803 ms |
6752 KB |
Output is correct |
18 |
Correct |
77 ms |
5200 KB |
Output is correct |
19 |
Correct |
812 ms |
6740 KB |
Output is correct |
20 |
Correct |
784 ms |
6560 KB |
Output is correct |
21 |
Correct |
765 ms |
6804 KB |
Output is correct |
22 |
Correct |
748 ms |
6736 KB |
Output is correct |
23 |
Correct |
1034 ms |
7084 KB |
Output is correct |
24 |
Correct |
637 ms |
5972 KB |
Output is correct |
25 |
Correct |
625 ms |
5968 KB |
Output is correct |
26 |
Correct |
1204 ms |
7308 KB |
Output is correct |
27 |
Correct |
1311 ms |
7072 KB |
Output is correct |
28 |
Correct |
1337 ms |
7684 KB |
Output is correct |
29 |
Correct |
1391 ms |
6924 KB |
Output is correct |
30 |
Correct |
1295 ms |
7312 KB |
Output is correct |
31 |
Correct |
1291 ms |
7252 KB |
Output is correct |
32 |
Correct |
1252 ms |
7236 KB |
Output is correct |
33 |
Correct |
1263 ms |
7368 KB |
Output is correct |
34 |
Correct |
1349 ms |
7180 KB |
Output is correct |
35 |
Correct |
1232 ms |
7552 KB |
Output is correct |
36 |
Correct |
1237 ms |
6984 KB |
Output is correct |
37 |
Correct |
1159 ms |
6904 KB |
Output is correct |
38 |
Correct |
1139 ms |
6992 KB |
Output is correct |
39 |
Correct |
1142 ms |
7672 KB |
Output is correct |
40 |
Correct |
1155 ms |
7396 KB |
Output is correct |
41 |
Correct |
1188 ms |
7188 KB |
Output is correct |
42 |
Correct |
1014 ms |
6788 KB |
Output is correct |
43 |
Correct |
1018 ms |
6724 KB |
Output is correct |
44 |
Correct |
1059 ms |
7080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
2 ms |
4700 KB |
Output is correct |
3 |
Correct |
21 ms |
4696 KB |
Output is correct |
4 |
Correct |
8 ms |
4952 KB |
Output is correct |
5 |
Correct |
22 ms |
4700 KB |
Output is correct |
6 |
Correct |
17 ms |
4696 KB |
Output is correct |
7 |
Correct |
18 ms |
4788 KB |
Output is correct |
8 |
Correct |
25 ms |
4700 KB |
Output is correct |
9 |
Correct |
16 ms |
4700 KB |
Output is correct |
10 |
Correct |
28 ms |
4700 KB |
Output is correct |
11 |
Correct |
26 ms |
4700 KB |
Output is correct |
12 |
Correct |
27 ms |
4696 KB |
Output is correct |
13 |
Correct |
34 ms |
4792 KB |
Output is correct |
14 |
Correct |
25 ms |
4700 KB |
Output is correct |
15 |
Correct |
35 ms |
4700 KB |
Output is correct |
16 |
Correct |
26 ms |
4696 KB |
Output is correct |
17 |
Correct |
26 ms |
4696 KB |
Output is correct |
18 |
Correct |
1237 ms |
7496 KB |
Output is correct |
19 |
Correct |
1224 ms |
7292 KB |
Output is correct |
20 |
Correct |
1187 ms |
7400 KB |
Output is correct |
21 |
Correct |
1234 ms |
7372 KB |
Output is correct |
22 |
Correct |
1269 ms |
7508 KB |
Output is correct |
23 |
Correct |
1258 ms |
6948 KB |
Output is correct |
24 |
Correct |
1296 ms |
6796 KB |
Output is correct |
25 |
Correct |
1851 ms |
6612 KB |
Output is correct |
26 |
Correct |
73 ms |
5232 KB |
Output is correct |
27 |
Correct |
1134 ms |
6652 KB |
Output is correct |
28 |
Correct |
1073 ms |
6920 KB |
Output is correct |
29 |
Correct |
1146 ms |
6988 KB |
Output is correct |
30 |
Correct |
1044 ms |
6740 KB |
Output is correct |
31 |
Correct |
780 ms |
6544 KB |
Output is correct |
32 |
Correct |
388 ms |
5456 KB |
Output is correct |
33 |
Correct |
787 ms |
6708 KB |
Output is correct |
34 |
Correct |
803 ms |
6752 KB |
Output is correct |
35 |
Correct |
77 ms |
5200 KB |
Output is correct |
36 |
Correct |
812 ms |
6740 KB |
Output is correct |
37 |
Correct |
784 ms |
6560 KB |
Output is correct |
38 |
Correct |
765 ms |
6804 KB |
Output is correct |
39 |
Correct |
748 ms |
6736 KB |
Output is correct |
40 |
Correct |
1034 ms |
7084 KB |
Output is correct |
41 |
Correct |
637 ms |
5972 KB |
Output is correct |
42 |
Correct |
625 ms |
5968 KB |
Output is correct |
43 |
Correct |
1785 ms |
10008 KB |
Output is correct |
44 |
Correct |
73 ms |
5204 KB |
Output is correct |
45 |
Correct |
203 ms |
7752 KB |
Output is correct |
46 |
Correct |
135 ms |
7768 KB |
Output is correct |
47 |
Correct |
1746 ms |
8524 KB |
Output is correct |
48 |
Correct |
1813 ms |
9664 KB |
Output is correct |
49 |
Correct |
1813 ms |
8444 KB |
Output is correct |
50 |
Correct |
868 ms |
7552 KB |
Output is correct |
51 |
Correct |
855 ms |
7464 KB |
Output is correct |
52 |
Correct |
816 ms |
6908 KB |
Output is correct |
53 |
Correct |
1296 ms |
8520 KB |
Output is correct |
54 |
Correct |
1328 ms |
8748 KB |
Output is correct |
55 |
Correct |
1371 ms |
7720 KB |
Output is correct |
56 |
Correct |
1770 ms |
8380 KB |
Output is correct |
57 |
Correct |
1745 ms |
8512 KB |
Output is correct |
58 |
Correct |
1876 ms |
9764 KB |
Output is correct |
59 |
Correct |
1845 ms |
9760 KB |
Output is correct |
60 |
Correct |
1876 ms |
9680 KB |
Output is correct |
61 |
Correct |
1816 ms |
9680 KB |
Output is correct |
62 |
Correct |
1573 ms |
8280 KB |
Output is correct |
63 |
Correct |
1557 ms |
7964 KB |
Output is correct |
64 |
Correct |
1804 ms |
9240 KB |
Output is correct |
65 |
Correct |
1394 ms |
8096 KB |
Output is correct |
66 |
Correct |
1204 ms |
7308 KB |
Output is correct |
67 |
Correct |
1311 ms |
7072 KB |
Output is correct |
68 |
Correct |
1337 ms |
7684 KB |
Output is correct |
69 |
Correct |
1391 ms |
6924 KB |
Output is correct |
70 |
Correct |
1295 ms |
7312 KB |
Output is correct |
71 |
Correct |
1291 ms |
7252 KB |
Output is correct |
72 |
Correct |
1252 ms |
7236 KB |
Output is correct |
73 |
Correct |
1263 ms |
7368 KB |
Output is correct |
74 |
Correct |
1349 ms |
7180 KB |
Output is correct |
75 |
Correct |
1232 ms |
7552 KB |
Output is correct |
76 |
Correct |
1237 ms |
6984 KB |
Output is correct |
77 |
Correct |
1159 ms |
6904 KB |
Output is correct |
78 |
Correct |
1139 ms |
6992 KB |
Output is correct |
79 |
Correct |
1142 ms |
7672 KB |
Output is correct |
80 |
Correct |
1155 ms |
7396 KB |
Output is correct |
81 |
Correct |
1188 ms |
7188 KB |
Output is correct |
82 |
Correct |
1014 ms |
6788 KB |
Output is correct |
83 |
Correct |
1018 ms |
6724 KB |
Output is correct |
84 |
Correct |
1059 ms |
7080 KB |
Output is correct |
85 |
Correct |
2644 ms |
9320 KB |
Output is correct |
86 |
Correct |
259 ms |
9560 KB |
Output is correct |
87 |
Correct |
147 ms |
9812 KB |
Output is correct |
88 |
Correct |
2691 ms |
10440 KB |
Output is correct |
89 |
Correct |
2593 ms |
13096 KB |
Output is correct |
90 |
Correct |
2600 ms |
10572 KB |
Output is correct |
91 |
Correct |
1452 ms |
10432 KB |
Output is correct |
92 |
Correct |
1275 ms |
10244 KB |
Output is correct |
93 |
Correct |
1321 ms |
9156 KB |
Output is correct |
94 |
Correct |
1981 ms |
11412 KB |
Output is correct |
95 |
Correct |
2004 ms |
11680 KB |
Output is correct |
96 |
Correct |
2125 ms |
10552 KB |
Output is correct |
97 |
Correct |
2592 ms |
10612 KB |
Output is correct |
98 |
Correct |
2637 ms |
10368 KB |
Output is correct |
99 |
Correct |
2852 ms |
13060 KB |
Output is correct |
100 |
Correct |
2729 ms |
12972 KB |
Output is correct |
101 |
Correct |
2724 ms |
13092 KB |
Output is correct |
102 |
Correct |
2989 ms |
13108 KB |
Output is correct |
103 |
Correct |
2296 ms |
10932 KB |
Output is correct |
104 |
Correct |
2780 ms |
10996 KB |
Output is correct |
105 |
Correct |
2084 ms |
10936 KB |
Output is correct |
106 |
Correct |
1707 ms |
10416 KB |
Output is correct |
107 |
Correct |
2138 ms |
11068 KB |
Output is correct |
108 |
Correct |
2576 ms |
12368 KB |
Output is correct |
109 |
Correct |
2185 ms |
9612 KB |
Output is correct |