#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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=600;
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 |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
21 ms |
796 KB |
Output is correct |
4 |
Correct |
5 ms |
524 KB |
Output is correct |
5 |
Correct |
10 ms |
664 KB |
Output is correct |
6 |
Correct |
9 ms |
596 KB |
Output is correct |
7 |
Correct |
12 ms |
596 KB |
Output is correct |
8 |
Correct |
13 ms |
636 KB |
Output is correct |
9 |
Correct |
14 ms |
724 KB |
Output is correct |
10 |
Correct |
13 ms |
656 KB |
Output is correct |
11 |
Correct |
13 ms |
560 KB |
Output is correct |
12 |
Correct |
16 ms |
596 KB |
Output is correct |
13 |
Correct |
18 ms |
692 KB |
Output is correct |
14 |
Correct |
17 ms |
596 KB |
Output is correct |
15 |
Correct |
15 ms |
668 KB |
Output is correct |
16 |
Correct |
12 ms |
596 KB |
Output is correct |
17 |
Correct |
13 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1264 ms |
4648 KB |
Output is correct |
2 |
Correct |
1268 ms |
4584 KB |
Output is correct |
3 |
Correct |
1315 ms |
4600 KB |
Output is correct |
4 |
Correct |
1312 ms |
4712 KB |
Output is correct |
5 |
Correct |
1262 ms |
4840 KB |
Output is correct |
6 |
Correct |
1779 ms |
5328 KB |
Output is correct |
7 |
Correct |
1740 ms |
5500 KB |
Output is correct |
8 |
Correct |
1737 ms |
5276 KB |
Output is correct |
9 |
Correct |
31 ms |
2412 KB |
Output is correct |
10 |
Correct |
958 ms |
5096 KB |
Output is correct |
11 |
Correct |
941 ms |
4860 KB |
Output is correct |
12 |
Correct |
1250 ms |
5408 KB |
Output is correct |
13 |
Correct |
1291 ms |
5096 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
960 ms |
3816 KB |
Output is correct |
2 |
Correct |
623 ms |
3184 KB |
Output is correct |
3 |
Correct |
1157 ms |
3992 KB |
Output is correct |
4 |
Correct |
1024 ms |
3828 KB |
Output is correct |
5 |
Correct |
35 ms |
2508 KB |
Output is correct |
6 |
Correct |
1113 ms |
3924 KB |
Output is correct |
7 |
Correct |
956 ms |
3848 KB |
Output is correct |
8 |
Correct |
863 ms |
3820 KB |
Output is correct |
9 |
Correct |
742 ms |
4092 KB |
Output is correct |
10 |
Correct |
770 ms |
3908 KB |
Output is correct |
11 |
Correct |
805 ms |
3640 KB |
Output is correct |
12 |
Correct |
713 ms |
3576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2169 ms |
6400 KB |
Output is correct |
2 |
Correct |
31 ms |
2516 KB |
Output is correct |
3 |
Correct |
208 ms |
4444 KB |
Output is correct |
4 |
Correct |
106 ms |
4448 KB |
Output is correct |
5 |
Correct |
1273 ms |
6340 KB |
Output is correct |
6 |
Correct |
2008 ms |
6320 KB |
Output is correct |
7 |
Correct |
1249 ms |
6380 KB |
Output is correct |
8 |
Correct |
951 ms |
4460 KB |
Output is correct |
9 |
Correct |
930 ms |
4400 KB |
Output is correct |
10 |
Correct |
995 ms |
5008 KB |
Output is correct |
11 |
Correct |
1589 ms |
5804 KB |
Output is correct |
12 |
Correct |
1607 ms |
5860 KB |
Output is correct |
13 |
Correct |
1633 ms |
5800 KB |
Output is correct |
14 |
Correct |
1112 ms |
6304 KB |
Output is correct |
15 |
Correct |
1171 ms |
6464 KB |
Output is correct |
16 |
Correct |
2172 ms |
6316 KB |
Output is correct |
17 |
Correct |
2121 ms |
6376 KB |
Output is correct |
18 |
Correct |
1978 ms |
6228 KB |
Output is correct |
19 |
Correct |
1978 ms |
6484 KB |
Output is correct |
20 |
Correct |
1716 ms |
5924 KB |
Output is correct |
21 |
Correct |
1837 ms |
5936 KB |
Output is correct |
22 |
Correct |
2049 ms |
6480 KB |
Output is correct |
23 |
Correct |
1228 ms |
5920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1264 ms |
4648 KB |
Output is correct |
2 |
Correct |
1268 ms |
4584 KB |
Output is correct |
3 |
Correct |
1315 ms |
4600 KB |
Output is correct |
4 |
Correct |
1312 ms |
4712 KB |
Output is correct |
5 |
Correct |
1262 ms |
4840 KB |
Output is correct |
6 |
Correct |
1779 ms |
5328 KB |
Output is correct |
7 |
Correct |
1740 ms |
5500 KB |
Output is correct |
8 |
Correct |
1737 ms |
5276 KB |
Output is correct |
9 |
Correct |
31 ms |
2412 KB |
Output is correct |
10 |
Correct |
958 ms |
5096 KB |
Output is correct |
11 |
Correct |
941 ms |
4860 KB |
Output is correct |
12 |
Correct |
1250 ms |
5408 KB |
Output is correct |
13 |
Correct |
1291 ms |
5096 KB |
Output is correct |
14 |
Correct |
960 ms |
3816 KB |
Output is correct |
15 |
Correct |
623 ms |
3184 KB |
Output is correct |
16 |
Correct |
1157 ms |
3992 KB |
Output is correct |
17 |
Correct |
1024 ms |
3828 KB |
Output is correct |
18 |
Correct |
35 ms |
2508 KB |
Output is correct |
19 |
Correct |
1113 ms |
3924 KB |
Output is correct |
20 |
Correct |
956 ms |
3848 KB |
Output is correct |
21 |
Correct |
863 ms |
3820 KB |
Output is correct |
22 |
Correct |
742 ms |
4092 KB |
Output is correct |
23 |
Correct |
770 ms |
3908 KB |
Output is correct |
24 |
Correct |
805 ms |
3640 KB |
Output is correct |
25 |
Correct |
713 ms |
3576 KB |
Output is correct |
26 |
Correct |
1260 ms |
4724 KB |
Output is correct |
27 |
Correct |
1609 ms |
4812 KB |
Output is correct |
28 |
Correct |
1450 ms |
4644 KB |
Output is correct |
29 |
Correct |
1086 ms |
4544 KB |
Output is correct |
30 |
Correct |
1503 ms |
4668 KB |
Output is correct |
31 |
Correct |
1432 ms |
4668 KB |
Output is correct |
32 |
Correct |
1501 ms |
4872 KB |
Output is correct |
33 |
Correct |
1392 ms |
4528 KB |
Output is correct |
34 |
Correct |
1379 ms |
4608 KB |
Output is correct |
35 |
Correct |
1370 ms |
4608 KB |
Output is correct |
36 |
Correct |
1100 ms |
4396 KB |
Output is correct |
37 |
Correct |
1112 ms |
4492 KB |
Output is correct |
38 |
Correct |
1129 ms |
4380 KB |
Output is correct |
39 |
Correct |
1033 ms |
4572 KB |
Output is correct |
40 |
Correct |
967 ms |
4484 KB |
Output is correct |
41 |
Correct |
1029 ms |
4388 KB |
Output is correct |
42 |
Correct |
1040 ms |
4520 KB |
Output is correct |
43 |
Correct |
998 ms |
4388 KB |
Output is correct |
44 |
Correct |
1010 ms |
4304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
21 ms |
796 KB |
Output is correct |
4 |
Correct |
5 ms |
524 KB |
Output is correct |
5 |
Correct |
10 ms |
664 KB |
Output is correct |
6 |
Correct |
9 ms |
596 KB |
Output is correct |
7 |
Correct |
12 ms |
596 KB |
Output is correct |
8 |
Correct |
13 ms |
636 KB |
Output is correct |
9 |
Correct |
14 ms |
724 KB |
Output is correct |
10 |
Correct |
13 ms |
656 KB |
Output is correct |
11 |
Correct |
13 ms |
560 KB |
Output is correct |
12 |
Correct |
16 ms |
596 KB |
Output is correct |
13 |
Correct |
18 ms |
692 KB |
Output is correct |
14 |
Correct |
17 ms |
596 KB |
Output is correct |
15 |
Correct |
15 ms |
668 KB |
Output is correct |
16 |
Correct |
12 ms |
596 KB |
Output is correct |
17 |
Correct |
13 ms |
596 KB |
Output is correct |
18 |
Correct |
1264 ms |
4648 KB |
Output is correct |
19 |
Correct |
1268 ms |
4584 KB |
Output is correct |
20 |
Correct |
1315 ms |
4600 KB |
Output is correct |
21 |
Correct |
1312 ms |
4712 KB |
Output is correct |
22 |
Correct |
1262 ms |
4840 KB |
Output is correct |
23 |
Correct |
1779 ms |
5328 KB |
Output is correct |
24 |
Correct |
1740 ms |
5500 KB |
Output is correct |
25 |
Correct |
1737 ms |
5276 KB |
Output is correct |
26 |
Correct |
31 ms |
2412 KB |
Output is correct |
27 |
Correct |
958 ms |
5096 KB |
Output is correct |
28 |
Correct |
941 ms |
4860 KB |
Output is correct |
29 |
Correct |
1250 ms |
5408 KB |
Output is correct |
30 |
Correct |
1291 ms |
5096 KB |
Output is correct |
31 |
Correct |
960 ms |
3816 KB |
Output is correct |
32 |
Correct |
623 ms |
3184 KB |
Output is correct |
33 |
Correct |
1157 ms |
3992 KB |
Output is correct |
34 |
Correct |
1024 ms |
3828 KB |
Output is correct |
35 |
Correct |
35 ms |
2508 KB |
Output is correct |
36 |
Correct |
1113 ms |
3924 KB |
Output is correct |
37 |
Correct |
956 ms |
3848 KB |
Output is correct |
38 |
Correct |
863 ms |
3820 KB |
Output is correct |
39 |
Correct |
742 ms |
4092 KB |
Output is correct |
40 |
Correct |
770 ms |
3908 KB |
Output is correct |
41 |
Correct |
805 ms |
3640 KB |
Output is correct |
42 |
Correct |
713 ms |
3576 KB |
Output is correct |
43 |
Correct |
2169 ms |
6400 KB |
Output is correct |
44 |
Correct |
31 ms |
2516 KB |
Output is correct |
45 |
Correct |
208 ms |
4444 KB |
Output is correct |
46 |
Correct |
106 ms |
4448 KB |
Output is correct |
47 |
Correct |
1273 ms |
6340 KB |
Output is correct |
48 |
Correct |
2008 ms |
6320 KB |
Output is correct |
49 |
Correct |
1249 ms |
6380 KB |
Output is correct |
50 |
Correct |
951 ms |
4460 KB |
Output is correct |
51 |
Correct |
930 ms |
4400 KB |
Output is correct |
52 |
Correct |
995 ms |
5008 KB |
Output is correct |
53 |
Correct |
1589 ms |
5804 KB |
Output is correct |
54 |
Correct |
1607 ms |
5860 KB |
Output is correct |
55 |
Correct |
1633 ms |
5800 KB |
Output is correct |
56 |
Correct |
1112 ms |
6304 KB |
Output is correct |
57 |
Correct |
1171 ms |
6464 KB |
Output is correct |
58 |
Correct |
2172 ms |
6316 KB |
Output is correct |
59 |
Correct |
2121 ms |
6376 KB |
Output is correct |
60 |
Correct |
1978 ms |
6228 KB |
Output is correct |
61 |
Correct |
1978 ms |
6484 KB |
Output is correct |
62 |
Correct |
1716 ms |
5924 KB |
Output is correct |
63 |
Correct |
1837 ms |
5936 KB |
Output is correct |
64 |
Correct |
2049 ms |
6480 KB |
Output is correct |
65 |
Correct |
1228 ms |
5920 KB |
Output is correct |
66 |
Correct |
1260 ms |
4724 KB |
Output is correct |
67 |
Correct |
1609 ms |
4812 KB |
Output is correct |
68 |
Correct |
1450 ms |
4644 KB |
Output is correct |
69 |
Correct |
1086 ms |
4544 KB |
Output is correct |
70 |
Correct |
1503 ms |
4668 KB |
Output is correct |
71 |
Correct |
1432 ms |
4668 KB |
Output is correct |
72 |
Correct |
1501 ms |
4872 KB |
Output is correct |
73 |
Correct |
1392 ms |
4528 KB |
Output is correct |
74 |
Correct |
1379 ms |
4608 KB |
Output is correct |
75 |
Correct |
1370 ms |
4608 KB |
Output is correct |
76 |
Correct |
1100 ms |
4396 KB |
Output is correct |
77 |
Correct |
1112 ms |
4492 KB |
Output is correct |
78 |
Correct |
1129 ms |
4380 KB |
Output is correct |
79 |
Correct |
1033 ms |
4572 KB |
Output is correct |
80 |
Correct |
967 ms |
4484 KB |
Output is correct |
81 |
Correct |
1029 ms |
4388 KB |
Output is correct |
82 |
Correct |
1040 ms |
4520 KB |
Output is correct |
83 |
Correct |
998 ms |
4388 KB |
Output is correct |
84 |
Correct |
1010 ms |
4304 KB |
Output is correct |
85 |
Correct |
2168 ms |
6692 KB |
Output is correct |
86 |
Correct |
239 ms |
4692 KB |
Output is correct |
87 |
Correct |
128 ms |
4476 KB |
Output is correct |
88 |
Correct |
1452 ms |
6960 KB |
Output is correct |
89 |
Correct |
2417 ms |
6740 KB |
Output is correct |
90 |
Correct |
1392 ms |
6620 KB |
Output is correct |
91 |
Correct |
1332 ms |
4596 KB |
Output is correct |
92 |
Correct |
1289 ms |
4524 KB |
Output is correct |
93 |
Correct |
1804 ms |
5436 KB |
Output is correct |
94 |
Correct |
1963 ms |
6016 KB |
Output is correct |
95 |
Correct |
1824 ms |
5916 KB |
Output is correct |
96 |
Correct |
1978 ms |
6436 KB |
Output is correct |
97 |
Correct |
1114 ms |
6800 KB |
Output is correct |
98 |
Correct |
1249 ms |
6552 KB |
Output is correct |
99 |
Correct |
2226 ms |
6816 KB |
Output is correct |
100 |
Correct |
2235 ms |
6608 KB |
Output is correct |
101 |
Correct |
2238 ms |
6828 KB |
Output is correct |
102 |
Correct |
2197 ms |
6480 KB |
Output is correct |
103 |
Correct |
2187 ms |
6204 KB |
Output is correct |
104 |
Correct |
2132 ms |
6468 KB |
Output is correct |
105 |
Correct |
1864 ms |
5952 KB |
Output is correct |
106 |
Correct |
1605 ms |
5748 KB |
Output is correct |
107 |
Correct |
1671 ms |
6524 KB |
Output is correct |
108 |
Correct |
2196 ms |
6880 KB |
Output is correct |
109 |
Correct |
1444 ms |
6708 KB |
Output is correct |