#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)a;++i)
#define rep3(i,a,b) for(ll i=a;i<(ll)b;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define lb(v,x) lower_bound(all(v),x);
#define ub(v,x) upper_bound(all(v),x);
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>
inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>
inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
struct dsu{
private:
vector<int>p;
vector<pair<int,int>>history;
public:
dsu(int n):p(n,-1){}
int root(int x){return (p[x]<0?x:root(p[x]));}
int size(int a){return -p[root(a)];}
void merge(int u,int v){
u=root(u),v=root(v);
if(u==v)return ;
if(p[u]>p[v])swap(u,v);
history.emplace_back(v,p[v]);
p[u]+=p[v];
p[v]=u;
}
void snapshot(){history.clear();}
void rollback(){
while(history.size()){
auto [u,sz]=history.back();history.pop_back();
p[p[u]]-=sz;
p[u]=sz;
}
}
};
struct edge{
int u,v,w;
};
struct query{
int t,x,w,idx;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;cin>>n>>m;
vector<edge>es(m);
rep(i,m){
int u,v,w;cin>>u>>v>>w;u--,v--;
es[i]=edge{u,v,w};
}
int q;cin>>q;
vector<query>qs(q);
vector<int>ans(q);
rep(i,q){
cin>>qs[i].t>>qs[i].x>>qs[i].w;
qs[i].idx=i;
qs[i].x--;
}
constexpr int B=500;
for(int l=0;l<q;l+=B){
const int r=min(q,l+B);
const int sz=r-l;
vector<bool>changed(m,false);
vector<query>qu;
rep(i,l,r){
if(qs[i].t==1)changed[qs[i].x]=1;
else qu.emplace_back(qs[i]);
}
vector<edge>pre;
vector<int>chg;
rep(i,m){
//cerr<<changed[i]<<" ";
if(changed[i])chg.push_back(i);
else pre.push_back(es[i]);
}//cerr<<endl;
sort(all(pre),[](const auto&l,const auto&r){
return l.w<r.w;
});
sort(all(qu),[](const auto&l,const auto&r){
return l.w>r.w;
});
vector<vector<int>>merge(sz);
rep(i,l,r){
if(qs[i].t==1)es[qs[i].x].w=qs[i].w;
else for(auto j:chg)if(es[j].w>=qs[i].w)merge[i-l].emplace_back(j);
}
dsu d(n);
for(auto [t,x,w,idx]:qu){
//cerr<<t<<" "<<x<<" "<<w<<" "<<idx<<endl;
while(!pre.empty()&&pre.back().w>=w){
//cerr<<pre.back().u<<" "<<pre.back().v<<" "<<pre.back().w<<endl;
d.merge(pre.back().u,pre.back().v);
pre.pop_back();
}
d.snapshot();
//cerr<<1<<endl;
for(auto j:merge[idx-l]){
//cerr<<es[j].u<<" "<<es[j].v<<endl;
d.merge(es[j].u,es[j].v);
}
ans[idx]=d.size(x);
d.rollback();
}
}
rep(i,q)if(qs[i].t==2)cout<<ans[i]<<"\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
19 ms |
916 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
10 ms |
712 KB |
Output is correct |
6 |
Correct |
8 ms |
684 KB |
Output is correct |
7 |
Correct |
11 ms |
716 KB |
Output is correct |
8 |
Correct |
12 ms |
724 KB |
Output is correct |
9 |
Correct |
13 ms |
716 KB |
Output is correct |
10 |
Correct |
15 ms |
724 KB |
Output is correct |
11 |
Correct |
13 ms |
724 KB |
Output is correct |
12 |
Correct |
15 ms |
692 KB |
Output is correct |
13 |
Correct |
16 ms |
828 KB |
Output is correct |
14 |
Correct |
14 ms |
796 KB |
Output is correct |
15 |
Correct |
13 ms |
724 KB |
Output is correct |
16 |
Correct |
12 ms |
740 KB |
Output is correct |
17 |
Correct |
12 ms |
736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1259 ms |
7216 KB |
Output is correct |
2 |
Correct |
1286 ms |
7256 KB |
Output is correct |
3 |
Correct |
1264 ms |
7400 KB |
Output is correct |
4 |
Correct |
1345 ms |
7508 KB |
Output is correct |
5 |
Correct |
1304 ms |
7232 KB |
Output is correct |
6 |
Correct |
1651 ms |
7876 KB |
Output is correct |
7 |
Correct |
1654 ms |
7840 KB |
Output is correct |
8 |
Correct |
1619 ms |
8200 KB |
Output is correct |
9 |
Correct |
36 ms |
3788 KB |
Output is correct |
10 |
Correct |
848 ms |
6420 KB |
Output is correct |
11 |
Correct |
844 ms |
6400 KB |
Output is correct |
12 |
Correct |
1242 ms |
7696 KB |
Output is correct |
13 |
Correct |
1258 ms |
7776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
909 ms |
6384 KB |
Output is correct |
2 |
Correct |
446 ms |
4632 KB |
Output is correct |
3 |
Correct |
987 ms |
6092 KB |
Output is correct |
4 |
Correct |
891 ms |
6204 KB |
Output is correct |
5 |
Correct |
32 ms |
3788 KB |
Output is correct |
6 |
Correct |
975 ms |
6352 KB |
Output is correct |
7 |
Correct |
850 ms |
6232 KB |
Output is correct |
8 |
Correct |
820 ms |
6020 KB |
Output is correct |
9 |
Correct |
748 ms |
6256 KB |
Output is correct |
10 |
Correct |
743 ms |
6012 KB |
Output is correct |
11 |
Correct |
764 ms |
6052 KB |
Output is correct |
12 |
Correct |
707 ms |
5980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2333 ms |
10144 KB |
Output is correct |
2 |
Correct |
45 ms |
3800 KB |
Output is correct |
3 |
Correct |
253 ms |
6268 KB |
Output is correct |
4 |
Correct |
122 ms |
6472 KB |
Output is correct |
5 |
Correct |
1390 ms |
8572 KB |
Output is correct |
6 |
Correct |
2268 ms |
10268 KB |
Output is correct |
7 |
Correct |
1365 ms |
8596 KB |
Output is correct |
8 |
Correct |
1101 ms |
6940 KB |
Output is correct |
9 |
Correct |
1083 ms |
7188 KB |
Output is correct |
10 |
Correct |
1123 ms |
7208 KB |
Output is correct |
11 |
Correct |
1864 ms |
9120 KB |
Output is correct |
12 |
Correct |
1747 ms |
9048 KB |
Output is correct |
13 |
Correct |
1849 ms |
8868 KB |
Output is correct |
14 |
Correct |
1356 ms |
8628 KB |
Output is correct |
15 |
Correct |
1375 ms |
8692 KB |
Output is correct |
16 |
Correct |
2371 ms |
10120 KB |
Output is correct |
17 |
Correct |
2364 ms |
10396 KB |
Output is correct |
18 |
Correct |
2338 ms |
10336 KB |
Output is correct |
19 |
Correct |
2299 ms |
10304 KB |
Output is correct |
20 |
Correct |
1947 ms |
9120 KB |
Output is correct |
21 |
Correct |
2024 ms |
9164 KB |
Output is correct |
22 |
Correct |
2302 ms |
9860 KB |
Output is correct |
23 |
Correct |
1396 ms |
8092 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1259 ms |
7216 KB |
Output is correct |
2 |
Correct |
1286 ms |
7256 KB |
Output is correct |
3 |
Correct |
1264 ms |
7400 KB |
Output is correct |
4 |
Correct |
1345 ms |
7508 KB |
Output is correct |
5 |
Correct |
1304 ms |
7232 KB |
Output is correct |
6 |
Correct |
1651 ms |
7876 KB |
Output is correct |
7 |
Correct |
1654 ms |
7840 KB |
Output is correct |
8 |
Correct |
1619 ms |
8200 KB |
Output is correct |
9 |
Correct |
36 ms |
3788 KB |
Output is correct |
10 |
Correct |
848 ms |
6420 KB |
Output is correct |
11 |
Correct |
844 ms |
6400 KB |
Output is correct |
12 |
Correct |
1242 ms |
7696 KB |
Output is correct |
13 |
Correct |
1258 ms |
7776 KB |
Output is correct |
14 |
Correct |
909 ms |
6384 KB |
Output is correct |
15 |
Correct |
446 ms |
4632 KB |
Output is correct |
16 |
Correct |
987 ms |
6092 KB |
Output is correct |
17 |
Correct |
891 ms |
6204 KB |
Output is correct |
18 |
Correct |
32 ms |
3788 KB |
Output is correct |
19 |
Correct |
975 ms |
6352 KB |
Output is correct |
20 |
Correct |
850 ms |
6232 KB |
Output is correct |
21 |
Correct |
820 ms |
6020 KB |
Output is correct |
22 |
Correct |
748 ms |
6256 KB |
Output is correct |
23 |
Correct |
743 ms |
6012 KB |
Output is correct |
24 |
Correct |
764 ms |
6052 KB |
Output is correct |
25 |
Correct |
707 ms |
5980 KB |
Output is correct |
26 |
Correct |
1229 ms |
7428 KB |
Output is correct |
27 |
Correct |
1454 ms |
7412 KB |
Output is correct |
28 |
Correct |
1395 ms |
7484 KB |
Output is correct |
29 |
Correct |
1187 ms |
7160 KB |
Output is correct |
30 |
Correct |
1396 ms |
7256 KB |
Output is correct |
31 |
Correct |
1428 ms |
7348 KB |
Output is correct |
32 |
Correct |
1457 ms |
7348 KB |
Output is correct |
33 |
Correct |
1256 ms |
7300 KB |
Output is correct |
34 |
Correct |
1327 ms |
7356 KB |
Output is correct |
35 |
Correct |
1271 ms |
7224 KB |
Output is correct |
36 |
Correct |
1195 ms |
7244 KB |
Output is correct |
37 |
Correct |
1150 ms |
7136 KB |
Output is correct |
38 |
Correct |
1170 ms |
7348 KB |
Output is correct |
39 |
Correct |
1075 ms |
7176 KB |
Output is correct |
40 |
Correct |
1079 ms |
7228 KB |
Output is correct |
41 |
Correct |
1104 ms |
7156 KB |
Output is correct |
42 |
Correct |
1102 ms |
7076 KB |
Output is correct |
43 |
Correct |
1036 ms |
7216 KB |
Output is correct |
44 |
Correct |
1051 ms |
7068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
19 ms |
916 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
10 ms |
712 KB |
Output is correct |
6 |
Correct |
8 ms |
684 KB |
Output is correct |
7 |
Correct |
11 ms |
716 KB |
Output is correct |
8 |
Correct |
12 ms |
724 KB |
Output is correct |
9 |
Correct |
13 ms |
716 KB |
Output is correct |
10 |
Correct |
15 ms |
724 KB |
Output is correct |
11 |
Correct |
13 ms |
724 KB |
Output is correct |
12 |
Correct |
15 ms |
692 KB |
Output is correct |
13 |
Correct |
16 ms |
828 KB |
Output is correct |
14 |
Correct |
14 ms |
796 KB |
Output is correct |
15 |
Correct |
13 ms |
724 KB |
Output is correct |
16 |
Correct |
12 ms |
740 KB |
Output is correct |
17 |
Correct |
12 ms |
736 KB |
Output is correct |
18 |
Correct |
1259 ms |
7216 KB |
Output is correct |
19 |
Correct |
1286 ms |
7256 KB |
Output is correct |
20 |
Correct |
1264 ms |
7400 KB |
Output is correct |
21 |
Correct |
1345 ms |
7508 KB |
Output is correct |
22 |
Correct |
1304 ms |
7232 KB |
Output is correct |
23 |
Correct |
1651 ms |
7876 KB |
Output is correct |
24 |
Correct |
1654 ms |
7840 KB |
Output is correct |
25 |
Correct |
1619 ms |
8200 KB |
Output is correct |
26 |
Correct |
36 ms |
3788 KB |
Output is correct |
27 |
Correct |
848 ms |
6420 KB |
Output is correct |
28 |
Correct |
844 ms |
6400 KB |
Output is correct |
29 |
Correct |
1242 ms |
7696 KB |
Output is correct |
30 |
Correct |
1258 ms |
7776 KB |
Output is correct |
31 |
Correct |
909 ms |
6384 KB |
Output is correct |
32 |
Correct |
446 ms |
4632 KB |
Output is correct |
33 |
Correct |
987 ms |
6092 KB |
Output is correct |
34 |
Correct |
891 ms |
6204 KB |
Output is correct |
35 |
Correct |
32 ms |
3788 KB |
Output is correct |
36 |
Correct |
975 ms |
6352 KB |
Output is correct |
37 |
Correct |
850 ms |
6232 KB |
Output is correct |
38 |
Correct |
820 ms |
6020 KB |
Output is correct |
39 |
Correct |
748 ms |
6256 KB |
Output is correct |
40 |
Correct |
743 ms |
6012 KB |
Output is correct |
41 |
Correct |
764 ms |
6052 KB |
Output is correct |
42 |
Correct |
707 ms |
5980 KB |
Output is correct |
43 |
Correct |
2333 ms |
10144 KB |
Output is correct |
44 |
Correct |
45 ms |
3800 KB |
Output is correct |
45 |
Correct |
253 ms |
6268 KB |
Output is correct |
46 |
Correct |
122 ms |
6472 KB |
Output is correct |
47 |
Correct |
1390 ms |
8572 KB |
Output is correct |
48 |
Correct |
2268 ms |
10268 KB |
Output is correct |
49 |
Correct |
1365 ms |
8596 KB |
Output is correct |
50 |
Correct |
1101 ms |
6940 KB |
Output is correct |
51 |
Correct |
1083 ms |
7188 KB |
Output is correct |
52 |
Correct |
1123 ms |
7208 KB |
Output is correct |
53 |
Correct |
1864 ms |
9120 KB |
Output is correct |
54 |
Correct |
1747 ms |
9048 KB |
Output is correct |
55 |
Correct |
1849 ms |
8868 KB |
Output is correct |
56 |
Correct |
1356 ms |
8628 KB |
Output is correct |
57 |
Correct |
1375 ms |
8692 KB |
Output is correct |
58 |
Correct |
2371 ms |
10120 KB |
Output is correct |
59 |
Correct |
2364 ms |
10396 KB |
Output is correct |
60 |
Correct |
2338 ms |
10336 KB |
Output is correct |
61 |
Correct |
2299 ms |
10304 KB |
Output is correct |
62 |
Correct |
1947 ms |
9120 KB |
Output is correct |
63 |
Correct |
2024 ms |
9164 KB |
Output is correct |
64 |
Correct |
2302 ms |
9860 KB |
Output is correct |
65 |
Correct |
1396 ms |
8092 KB |
Output is correct |
66 |
Correct |
1229 ms |
7428 KB |
Output is correct |
67 |
Correct |
1454 ms |
7412 KB |
Output is correct |
68 |
Correct |
1395 ms |
7484 KB |
Output is correct |
69 |
Correct |
1187 ms |
7160 KB |
Output is correct |
70 |
Correct |
1396 ms |
7256 KB |
Output is correct |
71 |
Correct |
1428 ms |
7348 KB |
Output is correct |
72 |
Correct |
1457 ms |
7348 KB |
Output is correct |
73 |
Correct |
1256 ms |
7300 KB |
Output is correct |
74 |
Correct |
1327 ms |
7356 KB |
Output is correct |
75 |
Correct |
1271 ms |
7224 KB |
Output is correct |
76 |
Correct |
1195 ms |
7244 KB |
Output is correct |
77 |
Correct |
1150 ms |
7136 KB |
Output is correct |
78 |
Correct |
1170 ms |
7348 KB |
Output is correct |
79 |
Correct |
1075 ms |
7176 KB |
Output is correct |
80 |
Correct |
1079 ms |
7228 KB |
Output is correct |
81 |
Correct |
1104 ms |
7156 KB |
Output is correct |
82 |
Correct |
1102 ms |
7076 KB |
Output is correct |
83 |
Correct |
1036 ms |
7216 KB |
Output is correct |
84 |
Correct |
1051 ms |
7068 KB |
Output is correct |
85 |
Correct |
2495 ms |
10376 KB |
Output is correct |
86 |
Correct |
272 ms |
6468 KB |
Output is correct |
87 |
Correct |
149 ms |
6452 KB |
Output is correct |
88 |
Correct |
1480 ms |
9056 KB |
Output is correct |
89 |
Correct |
2473 ms |
10412 KB |
Output is correct |
90 |
Correct |
1466 ms |
9324 KB |
Output is correct |
91 |
Correct |
1349 ms |
7188 KB |
Output is correct |
92 |
Correct |
1305 ms |
7216 KB |
Output is correct |
93 |
Correct |
1649 ms |
7976 KB |
Output is correct |
94 |
Correct |
1900 ms |
9176 KB |
Output is correct |
95 |
Correct |
1882 ms |
9344 KB |
Output is correct |
96 |
Correct |
1969 ms |
9404 KB |
Output is correct |
97 |
Correct |
1339 ms |
9056 KB |
Output is correct |
98 |
Correct |
1432 ms |
8644 KB |
Output is correct |
99 |
Correct |
2459 ms |
10240 KB |
Output is correct |
100 |
Correct |
2409 ms |
10304 KB |
Output is correct |
101 |
Correct |
2510 ms |
10472 KB |
Output is correct |
102 |
Correct |
2484 ms |
10332 KB |
Output is correct |
103 |
Correct |
2257 ms |
9928 KB |
Output is correct |
104 |
Correct |
2204 ms |
9828 KB |
Output is correct |
105 |
Correct |
2153 ms |
9408 KB |
Output is correct |
106 |
Correct |
1871 ms |
8968 KB |
Output is correct |
107 |
Correct |
1968 ms |
9656 KB |
Output is correct |
108 |
Correct |
2372 ms |
10296 KB |
Output is correct |
109 |
Correct |
1504 ms |
8284 KB |
Output is correct |