#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define per(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=1e5+99,S=433;
int n,m,q,act[N],actsz,a[N],b[N],s[N],t[N],w[N],pw[N],cw[N],par[N],rap[N],ans[N],mark[N],type[N];
vector<int> v[N];
bool cmp(int i,int j){
return b[i]>b[j];
}
void reset(){
rep(i,0,actsz){
par[act[i]]=rap[act[i]];
}
actsz=0;
}
inline int getpar(int u,int s){
while(par[u]>0){
u=par[u];
}
return u;
}
inline void merge(int u,int v,int s){
u=getpar(u,s),v=getpar(v,s);
if(u==v) return ;
if(par[u]>par[v]) swap(u,v);
if(s==0){
par[u]+=par[v];
rap[u]+=rap[v];
par[v]=u;
rap[v]=u;
}
else{
act[actsz++]=u;
act[actsz++]=v;
par[u]+=par[v];
par[v]=u;
}
}
void solve(int l,int r){
fill(mark,mark+m,0);
fill(par,par+n+10,-1);
fill(rap,rap+n+10,-1);
vector<int> vec;
rep(i,0,m){
w[i]=cw[i];
}
rep(i,0,l){
if(type[i]==1){
w[a[i]]=b[i];
}
}
rep(i,0,m){
pw[i]=w[i];
}
rep(i,l,r){
if(type[i]==1){
mark[a[i]]=1;
}
else{
vec.pb(i);
}
}
int p=N-1;
rep(i,0,m){
if(!mark[i]){
v[w[i]].pb(i);
}
}
sort(all(vec),cmp);
for(auto id : vec){
rep(i,l,id){
if(type[i]==1){
pw[a[i]]=b[i];
}
}
while(b[id]<=p){
for(auto x : v[p]){
merge(s[x],t[x],0);
}
p--;
}
rep(i,l,r){
if(b[id]<=pw[a[i]]){
merge(s[a[i]],t[a[i]],1);
}
}
ans[id]=-par[getpar(a[id],1)];
rep(i,l,id){
if(type[i]==1){
pw[a[i]]=w[a[i]];
}
}
reset();
}
rep(i,0,N){
v[i].clear();
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
srand(time(NULL));
vector<int> vec; vec.pb(-1);
cin>>n>>m;
rep(i,0,m){
cin>>s[i]>>t[i]>>w[i];
}
cin>>q;
rep(i,0,q){
cin>>type[i]>>a[i]>>b[i];
if(type[i]==1) a[i]--;
vec.pb(b[i]);
}
sort(all(vec));
rep(i,0,m){
w[i]=upper_bound(all(vec),w[i])-vec.begin()-1;
cw[i]=w[i];
}
rep(i,0,q){
b[i]=upper_bound(all(vec),b[i])-vec.begin()-1;
}
for(int i=0;i<q;i+=S){
solve(i,min(q,i+S));
}
rep(i,0,q){
if(type[i]==1) continue ;
cout<<ans[i]<<" ";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2676 KB |
Output is correct |
3 |
Correct |
34 ms |
3112 KB |
Output is correct |
4 |
Correct |
16 ms |
3020 KB |
Output is correct |
5 |
Correct |
36 ms |
3216 KB |
Output is correct |
6 |
Correct |
28 ms |
3120 KB |
Output is correct |
7 |
Correct |
29 ms |
3060 KB |
Output is correct |
8 |
Correct |
36 ms |
3104 KB |
Output is correct |
9 |
Correct |
30 ms |
3056 KB |
Output is correct |
10 |
Correct |
36 ms |
3020 KB |
Output is correct |
11 |
Correct |
37 ms |
3228 KB |
Output is correct |
12 |
Correct |
42 ms |
3092 KB |
Output is correct |
13 |
Correct |
41 ms |
3020 KB |
Output is correct |
14 |
Correct |
39 ms |
3020 KB |
Output is correct |
15 |
Correct |
42 ms |
3092 KB |
Output is correct |
16 |
Correct |
34 ms |
3020 KB |
Output is correct |
17 |
Correct |
41 ms |
3048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1496 ms |
8868 KB |
Output is correct |
2 |
Correct |
1530 ms |
8664 KB |
Output is correct |
3 |
Correct |
1524 ms |
8648 KB |
Output is correct |
4 |
Correct |
1517 ms |
8708 KB |
Output is correct |
5 |
Correct |
1564 ms |
8672 KB |
Output is correct |
6 |
Correct |
1536 ms |
8388 KB |
Output is correct |
7 |
Correct |
1543 ms |
8444 KB |
Output is correct |
8 |
Correct |
1539 ms |
8456 KB |
Output is correct |
9 |
Correct |
160 ms |
5268 KB |
Output is correct |
10 |
Correct |
717 ms |
6944 KB |
Output is correct |
11 |
Correct |
678 ms |
6980 KB |
Output is correct |
12 |
Correct |
1583 ms |
7468 KB |
Output is correct |
13 |
Correct |
1225 ms |
9284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1162 ms |
8044 KB |
Output is correct |
2 |
Correct |
630 ms |
6852 KB |
Output is correct |
3 |
Correct |
1136 ms |
7916 KB |
Output is correct |
4 |
Correct |
1134 ms |
7944 KB |
Output is correct |
5 |
Correct |
160 ms |
5152 KB |
Output is correct |
6 |
Correct |
1162 ms |
8008 KB |
Output is correct |
7 |
Correct |
1091 ms |
8024 KB |
Output is correct |
8 |
Correct |
1036 ms |
7816 KB |
Output is correct |
9 |
Correct |
1037 ms |
7204 KB |
Output is correct |
10 |
Correct |
991 ms |
7096 KB |
Output is correct |
11 |
Correct |
876 ms |
8724 KB |
Output is correct |
12 |
Correct |
837 ms |
8536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2415 ms |
9352 KB |
Output is correct |
2 |
Correct |
161 ms |
5080 KB |
Output is correct |
3 |
Correct |
171 ms |
5960 KB |
Output is correct |
4 |
Correct |
158 ms |
5824 KB |
Output is correct |
5 |
Correct |
1248 ms |
8572 KB |
Output is correct |
6 |
Correct |
2308 ms |
9452 KB |
Output is correct |
7 |
Correct |
1280 ms |
8596 KB |
Output is correct |
8 |
Correct |
1421 ms |
7404 KB |
Output is correct |
9 |
Correct |
1363 ms |
7508 KB |
Output is correct |
10 |
Correct |
1180 ms |
7156 KB |
Output is correct |
11 |
Correct |
2115 ms |
8456 KB |
Output is correct |
12 |
Correct |
1979 ms |
8492 KB |
Output is correct |
13 |
Correct |
1599 ms |
8128 KB |
Output is correct |
14 |
Correct |
1287 ms |
8752 KB |
Output is correct |
15 |
Correct |
1262 ms |
8708 KB |
Output is correct |
16 |
Correct |
2515 ms |
9608 KB |
Output is correct |
17 |
Correct |
2571 ms |
9596 KB |
Output is correct |
18 |
Correct |
2582 ms |
9408 KB |
Output is correct |
19 |
Correct |
2451 ms |
9412 KB |
Output is correct |
20 |
Correct |
1897 ms |
8096 KB |
Output is correct |
21 |
Correct |
1844 ms |
8120 KB |
Output is correct |
22 |
Correct |
2009 ms |
8932 KB |
Output is correct |
23 |
Correct |
1519 ms |
7948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1496 ms |
8868 KB |
Output is correct |
2 |
Correct |
1530 ms |
8664 KB |
Output is correct |
3 |
Correct |
1524 ms |
8648 KB |
Output is correct |
4 |
Correct |
1517 ms |
8708 KB |
Output is correct |
5 |
Correct |
1564 ms |
8672 KB |
Output is correct |
6 |
Correct |
1536 ms |
8388 KB |
Output is correct |
7 |
Correct |
1543 ms |
8444 KB |
Output is correct |
8 |
Correct |
1539 ms |
8456 KB |
Output is correct |
9 |
Correct |
160 ms |
5268 KB |
Output is correct |
10 |
Correct |
717 ms |
6944 KB |
Output is correct |
11 |
Correct |
678 ms |
6980 KB |
Output is correct |
12 |
Correct |
1583 ms |
7468 KB |
Output is correct |
13 |
Correct |
1225 ms |
9284 KB |
Output is correct |
14 |
Correct |
1162 ms |
8044 KB |
Output is correct |
15 |
Correct |
630 ms |
6852 KB |
Output is correct |
16 |
Correct |
1136 ms |
7916 KB |
Output is correct |
17 |
Correct |
1134 ms |
7944 KB |
Output is correct |
18 |
Correct |
160 ms |
5152 KB |
Output is correct |
19 |
Correct |
1162 ms |
8008 KB |
Output is correct |
20 |
Correct |
1091 ms |
8024 KB |
Output is correct |
21 |
Correct |
1036 ms |
7816 KB |
Output is correct |
22 |
Correct |
1037 ms |
7204 KB |
Output is correct |
23 |
Correct |
991 ms |
7096 KB |
Output is correct |
24 |
Correct |
876 ms |
8724 KB |
Output is correct |
25 |
Correct |
837 ms |
8536 KB |
Output is correct |
26 |
Correct |
1525 ms |
8412 KB |
Output is correct |
27 |
Correct |
1597 ms |
8336 KB |
Output is correct |
28 |
Correct |
1613 ms |
8624 KB |
Output is correct |
29 |
Correct |
1332 ms |
8256 KB |
Output is correct |
30 |
Correct |
1608 ms |
8308 KB |
Output is correct |
31 |
Correct |
1620 ms |
8436 KB |
Output is correct |
32 |
Correct |
1620 ms |
8292 KB |
Output is correct |
33 |
Correct |
1567 ms |
8540 KB |
Output is correct |
34 |
Correct |
1565 ms |
8496 KB |
Output is correct |
35 |
Correct |
1581 ms |
8348 KB |
Output is correct |
36 |
Correct |
1328 ms |
8164 KB |
Output is correct |
37 |
Correct |
1359 ms |
8256 KB |
Output is correct |
38 |
Correct |
1328 ms |
8132 KB |
Output is correct |
39 |
Correct |
1188 ms |
7568 KB |
Output is correct |
40 |
Correct |
1192 ms |
7440 KB |
Output is correct |
41 |
Correct |
1185 ms |
7476 KB |
Output is correct |
42 |
Correct |
1199 ms |
9180 KB |
Output is correct |
43 |
Correct |
1188 ms |
9132 KB |
Output is correct |
44 |
Correct |
1154 ms |
9024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2676 KB |
Output is correct |
3 |
Correct |
34 ms |
3112 KB |
Output is correct |
4 |
Correct |
16 ms |
3020 KB |
Output is correct |
5 |
Correct |
36 ms |
3216 KB |
Output is correct |
6 |
Correct |
28 ms |
3120 KB |
Output is correct |
7 |
Correct |
29 ms |
3060 KB |
Output is correct |
8 |
Correct |
36 ms |
3104 KB |
Output is correct |
9 |
Correct |
30 ms |
3056 KB |
Output is correct |
10 |
Correct |
36 ms |
3020 KB |
Output is correct |
11 |
Correct |
37 ms |
3228 KB |
Output is correct |
12 |
Correct |
42 ms |
3092 KB |
Output is correct |
13 |
Correct |
41 ms |
3020 KB |
Output is correct |
14 |
Correct |
39 ms |
3020 KB |
Output is correct |
15 |
Correct |
42 ms |
3092 KB |
Output is correct |
16 |
Correct |
34 ms |
3020 KB |
Output is correct |
17 |
Correct |
41 ms |
3048 KB |
Output is correct |
18 |
Correct |
1496 ms |
8868 KB |
Output is correct |
19 |
Correct |
1530 ms |
8664 KB |
Output is correct |
20 |
Correct |
1524 ms |
8648 KB |
Output is correct |
21 |
Correct |
1517 ms |
8708 KB |
Output is correct |
22 |
Correct |
1564 ms |
8672 KB |
Output is correct |
23 |
Correct |
1536 ms |
8388 KB |
Output is correct |
24 |
Correct |
1543 ms |
8444 KB |
Output is correct |
25 |
Correct |
1539 ms |
8456 KB |
Output is correct |
26 |
Correct |
160 ms |
5268 KB |
Output is correct |
27 |
Correct |
717 ms |
6944 KB |
Output is correct |
28 |
Correct |
678 ms |
6980 KB |
Output is correct |
29 |
Correct |
1583 ms |
7468 KB |
Output is correct |
30 |
Correct |
1225 ms |
9284 KB |
Output is correct |
31 |
Correct |
1162 ms |
8044 KB |
Output is correct |
32 |
Correct |
630 ms |
6852 KB |
Output is correct |
33 |
Correct |
1136 ms |
7916 KB |
Output is correct |
34 |
Correct |
1134 ms |
7944 KB |
Output is correct |
35 |
Correct |
160 ms |
5152 KB |
Output is correct |
36 |
Correct |
1162 ms |
8008 KB |
Output is correct |
37 |
Correct |
1091 ms |
8024 KB |
Output is correct |
38 |
Correct |
1036 ms |
7816 KB |
Output is correct |
39 |
Correct |
1037 ms |
7204 KB |
Output is correct |
40 |
Correct |
991 ms |
7096 KB |
Output is correct |
41 |
Correct |
876 ms |
8724 KB |
Output is correct |
42 |
Correct |
837 ms |
8536 KB |
Output is correct |
43 |
Correct |
2415 ms |
9352 KB |
Output is correct |
44 |
Correct |
161 ms |
5080 KB |
Output is correct |
45 |
Correct |
171 ms |
5960 KB |
Output is correct |
46 |
Correct |
158 ms |
5824 KB |
Output is correct |
47 |
Correct |
1248 ms |
8572 KB |
Output is correct |
48 |
Correct |
2308 ms |
9452 KB |
Output is correct |
49 |
Correct |
1280 ms |
8596 KB |
Output is correct |
50 |
Correct |
1421 ms |
7404 KB |
Output is correct |
51 |
Correct |
1363 ms |
7508 KB |
Output is correct |
52 |
Correct |
1180 ms |
7156 KB |
Output is correct |
53 |
Correct |
2115 ms |
8456 KB |
Output is correct |
54 |
Correct |
1979 ms |
8492 KB |
Output is correct |
55 |
Correct |
1599 ms |
8128 KB |
Output is correct |
56 |
Correct |
1287 ms |
8752 KB |
Output is correct |
57 |
Correct |
1262 ms |
8708 KB |
Output is correct |
58 |
Correct |
2515 ms |
9608 KB |
Output is correct |
59 |
Correct |
2571 ms |
9596 KB |
Output is correct |
60 |
Correct |
2582 ms |
9408 KB |
Output is correct |
61 |
Correct |
2451 ms |
9412 KB |
Output is correct |
62 |
Correct |
1897 ms |
8096 KB |
Output is correct |
63 |
Correct |
1844 ms |
8120 KB |
Output is correct |
64 |
Correct |
2009 ms |
8932 KB |
Output is correct |
65 |
Correct |
1519 ms |
7948 KB |
Output is correct |
66 |
Correct |
1525 ms |
8412 KB |
Output is correct |
67 |
Correct |
1597 ms |
8336 KB |
Output is correct |
68 |
Correct |
1613 ms |
8624 KB |
Output is correct |
69 |
Correct |
1332 ms |
8256 KB |
Output is correct |
70 |
Correct |
1608 ms |
8308 KB |
Output is correct |
71 |
Correct |
1620 ms |
8436 KB |
Output is correct |
72 |
Correct |
1620 ms |
8292 KB |
Output is correct |
73 |
Correct |
1567 ms |
8540 KB |
Output is correct |
74 |
Correct |
1565 ms |
8496 KB |
Output is correct |
75 |
Correct |
1581 ms |
8348 KB |
Output is correct |
76 |
Correct |
1328 ms |
8164 KB |
Output is correct |
77 |
Correct |
1359 ms |
8256 KB |
Output is correct |
78 |
Correct |
1328 ms |
8132 KB |
Output is correct |
79 |
Correct |
1188 ms |
7568 KB |
Output is correct |
80 |
Correct |
1192 ms |
7440 KB |
Output is correct |
81 |
Correct |
1185 ms |
7476 KB |
Output is correct |
82 |
Correct |
1199 ms |
9180 KB |
Output is correct |
83 |
Correct |
1188 ms |
9132 KB |
Output is correct |
84 |
Correct |
1154 ms |
9024 KB |
Output is correct |
85 |
Correct |
2619 ms |
9924 KB |
Output is correct |
86 |
Correct |
176 ms |
6116 KB |
Output is correct |
87 |
Correct |
122 ms |
5844 KB |
Output is correct |
88 |
Correct |
1288 ms |
8312 KB |
Output is correct |
89 |
Correct |
2487 ms |
9932 KB |
Output is correct |
90 |
Correct |
1285 ms |
8220 KB |
Output is correct |
91 |
Correct |
1579 ms |
8356 KB |
Output is correct |
92 |
Correct |
1657 ms |
8608 KB |
Output is correct |
93 |
Correct |
1627 ms |
8264 KB |
Output is correct |
94 |
Correct |
2226 ms |
9268 KB |
Output is correct |
95 |
Correct |
2173 ms |
9160 KB |
Output is correct |
96 |
Correct |
1967 ms |
8892 KB |
Output is correct |
97 |
Correct |
1291 ms |
8512 KB |
Output is correct |
98 |
Correct |
1032 ms |
8132 KB |
Output is correct |
99 |
Correct |
2635 ms |
9960 KB |
Output is correct |
100 |
Correct |
2713 ms |
9984 KB |
Output is correct |
101 |
Correct |
2668 ms |
10056 KB |
Output is correct |
102 |
Correct |
2631 ms |
9916 KB |
Output is correct |
103 |
Correct |
2150 ms |
8988 KB |
Output is correct |
104 |
Correct |
2156 ms |
9024 KB |
Output is correct |
105 |
Correct |
1982 ms |
10016 KB |
Output is correct |
106 |
Correct |
1721 ms |
9836 KB |
Output is correct |
107 |
Correct |
2143 ms |
8112 KB |
Output is correct |
108 |
Correct |
2405 ms |
9732 KB |
Output is correct |
109 |
Correct |
1373 ms |
7844 KB |
Output is correct |