제출 #440540

#제출 시각아이디문제언어결과실행 시간메모리
440540KULIKOLD다리 (APIO19_bridges)C++17
43 / 100
3037 ms7016 KiB
//#pragma GCC optimize ("O3") #include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' int n,m,q; const int DIM = 1E5+7; const int INF = 2E9; struct node{ int u,v,w; } edges[DIM],Q[DIM]; int P[DIM]; inline int F(int x){ return x==P[x]?x:P[x] = F(P[x]); } void solve(){ for(int i = 1;i<=q;++i){ int type = Q[i].u; if (type==1){ int pos,w; pos = Q[i].v,w = Q[i].w; edges[pos].w = w; continue; } int st,w; st = Q[i].v,w = Q[i].w; for(int j = 1;j<=n;++j) P[j] = j; for(int j = 1;j<=m;++j){ if (edges[j].w>=w) P[F(edges[j].u)] = F(edges[j].v); } int res = 0; for(int j = 1;j<=n;++j) res+=(F(j)==F(st)); cout<<res<<endl; } } int T[DIM*4]; void buildtree(int t,int tl,int tr){ if (tl==tr){ T[t] = edges[tl].w; return; } int tm = (tl+tr)/2; buildtree(t*2+1,tl,tm); buildtree(t*2+2,tm+1,tr); T[t] = min(T[t*2+1],T[t*2+2]); } int find_L(int t,int tl,int tr,int l,int r,int w){ if (tl>r || l>tr) return tl; if (l<=tl && tr<=r && T[t]>=w) return tl; if (tl==tr) return INF; int tm = (tl+tr)/2; int ret = find_L(t*2+2,tm+1,tr,l,r,w); if (ret==tm+1) return min(ret,find_L(t*2+1,tl,tm,l,r,w)); return ret; } int find_R(int t,int tl,int tr,int l,int r,int w){ if (tl>r || l>tr) return tr; if (l<=tl && tr<=r && T[t]>=w) return tr; if (tl==tr) return -1; int tm = (tl+tr)/2; int ret = find_R(t*2+1,tl,tm,l,r,w); if (ret==tm) return max(find_R(t*2+2,tm+1,tr,l,r,w),ret); return ret; } void update(int t,int tl,int tr,int pos,int val){ if (tl>pos || tr<pos) return; if (tl==tr){ T[t] = val; return; } int tm = (tl+tr)/2; update(t*2+1,tl,tm,pos,val); update(t*2+2,tm+1,tr,pos,val); T[t] = min(T[t*2+1],T[t*2+2]); } void solve1(){ buildtree(0,1,m); for(int i = 1;i<=q;++i){ int type = Q[i].u; if (type==1){ update(0,1,m,Q[i].v,Q[i].w); } else{ int w = Q[i].w,st = Q[i].v; int l = INF,r = 0; if (st>1) l = find_L(0,1,m,1,st-1,w); if (st<n) r = find_R(0,1,m,st,m,w)+1; if (l>st) l = st; if (r<st) r = st; cout<<r-l+1<<endl; } } } bool mc(node &a,node &b){ return a.w>b.w; } int ans[DIM],cnt[DIM]; void solve2(){ sort(edges+1,edges+1+m,mc); for(int i = 1;i<=q;++i){ Q[i].u = i; } for(int i = 1;i<=n;++i) P[i] = i,cnt[i] = 1; sort(Q+1,Q+1+q,mc); int ptr = 0; for(int i = 1;i<=q;++i){ while(ptr<m && edges[ptr+1].w>=Q[i].w){ ++ptr; if (F(edges[ptr].v)!=F(edges[ptr].u)) { cnt[F(edges[ptr].v)] += cnt[F(edges[ptr].u)]; P[F(edges[ptr].u)] = F(edges[ptr].v); } } ans[Q[i].u] = cnt[F(Q[i].v)]; } for(int i = 1;i<=q;++i) cout<<ans[i]<<endl; } vector<pair<ll,ll> > G[DIM]; int res = 0; void dfs(int v,int par,int w){ ++res; for(auto to:G[v]){ if (to.first==par) continue; if (edges[to.second].w>=w) dfs(to.first,v,w); } } void solve3(){ for(int i = 1;i<=m;++i){ G[edges[i].u].push_back({edges[i].v,i}); G[edges[i].v].push_back({edges[i].u,i}); } for(int i = 1;i<=q;++i){ if (Q[i].u==1){ edges[Q[i].v].w = Q[i].w; } else{ res = 0; dfs(Q[i].v,Q[i].v,Q[i].w); cout<<res<<endl; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; ll flag = 0; if (n-1!=m || m==0) flag = 1; for(int i = 1;i<=m;++i){ cin>>edges[i].u>>edges[i].v>>edges[i].w; if (edges[i].u!=edges[i].v-1 || edges[i].u!=i) flag = 1; } cin>>q; ll flag1 = 0; for(int i = 1;i<=q;++i){ cin>>Q[i].u>>Q[i].v>>Q[i].w; if (Q[i].u!=2) flag1 = 1; } if (m==0 || (n<=1000 && m<=1000 && q<=10000)) solve(); else if (flag==0) solve1(); else if (flag1==0)solve2(); else solve3(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...