제출 #196904

#제출 시각아이디문제언어결과실행 시간메모리
196904Andrei_Cotor다리 (APIO19_bridges)C++14
59 / 100
3064 ms7528 KiB
#include<iostream> #include<algorithm> #define BUCK 500 using namespace std; typedef struct edge { int x,y,c; } EDGE; typedef struct qry { int t,x,y,ind; } QRY; bool cmp(EDGE a, EDGE b) { return a.c>b.c; } bool cmp2(QRY a, QRY b) { return a.y>b.y; } EDGE Edges[100005],EdgeLeft[100005]; QRY Q[100005],Updates[BUCK+5],Queries[BUCK+5]; int Sz[50005],P[50005],top,Rez[100005]; bool Updated[100005],Viz[100005]; pair<int,int> S[BUCK+5]; int parent(int x) { while(P[x]!=0) x=P[x]; return x; } void unite(int x, int y, bool reversable) { x=parent(x); y=parent(y); if(x==y) return; if(Sz[x]>Sz[y]) { if(reversable) S[++top]={y,x}; Sz[x]+=Sz[y]; P[y]=x; } else { if(reversable) S[++top]={x,y}; Sz[y]+=Sz[x]; P[x]=y; } } void revDSU() { while(top) { P[S[top].first]=0; Sz[S[top].second]-=Sz[S[top].first]; top--; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; for(int i=1; i<=m; i++) cin>>Edges[i].x>>Edges[i].y>>Edges[i].c; int q; cin>>q; for(int i=1; i<=q; i++) { cin>>Q[i].t>>Q[i].x>>Q[i].y; Q[i].ind=i; } for(int st=1, dr=BUCK; st<=q; st+=BUCK, dr+=BUCK) { dr=min(dr,q); for(int i=1; i<=m; i++) Viz[i]=0; for(int i=1; i<=n; i++) { Sz[i]=1; P[i]=0; } int nru=0,nrq=0; for(int i=st; i<=dr; i++) { if(Q[i].t==1) { Updates[++nru]=Q[i]; Viz[Q[i].x]=1; } else Queries[++nrq]=Q[i]; } int nrel=0; for(int i=1; i<=m; i++) { if(!Viz[i]) EdgeLeft[++nrel]=Edges[i]; } sort(EdgeLeft+1,EdgeLeft+nrel+1,cmp); sort(Queries+1,Queries+nrq+1,cmp2); int ie=1; for(int iq=1; iq<=nrq; iq++) { while(ie<=nrel && Queries[iq].y<=EdgeLeft[ie].c) { unite(EdgeLeft[ie].x,EdgeLeft[ie].y,0); ie++; } for(int i=1; i<=nru; i++) Updated[Updates[i].x]=0; int start=1; while(start<=nru && Updates[start].ind<Queries[iq].ind) start++; for(int iu=start-1; iu>=1; iu--) { if(Updated[Updates[iu].x]) continue; Updated[Updates[iu].x]=1; if(Updates[iu].y>=Queries[iq].y) unite(Edges[Updates[iu].x].x,Edges[Updates[iu].x].y,1); } for(int iu=start; iu<=nru; iu++) { if(Updated[Updates[iu].x]) continue; if(Edges[Updates[iu].x].c>=Queries[iq].y) unite(Edges[Updates[iu].x].x,Edges[Updates[iu].x].y,1); } Rez[Queries[iq].ind]=Sz[parent(Queries[iq].x)]; revDSU(); } for(int i=1; i<=nru; i++) Edges[Updates[i].x].c=Updates[i].y; } for(int i=1; i<=q; i++) { if(Q[i].t==2) cout<<Rez[i]<<"\n"; } 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...