제출 #732396

#제출 시각아이디문제언어결과실행 시간메모리
732396bin9638자매 도시 (APIO20_swap)C++17
0 / 100
2066 ms9684 KiB
#include <bits/stdc++.h> #ifndef SKY #include "swap.h" #endif // SKY using namespace std; #define N 200010 #define ll long long #define fs first #define sc second #define ii pair<int,int> #define pb push_back vector<ii>g[N]; vector<int>f[N]; int sz[N],n,m,head[N],times,LOG,chain,in[N],pos[N],picked[N],MV[N]; ii cha[N][21],cnt[N]; struct IT { int ST[N*4]; void init() { for(int i=1;i<=n*4;i++) ST[i]=2e9; } void update(int id,int l,int r,int i,int val) { if(l>i||r<i) return; if(l==r) { ST[id]=val; return; } int mid=(l+r)/2; update(id*2,l,mid,i,val); update(id*2+1,mid+1,r,i,val); ST[id]=min(ST[id*2],ST[id*2+1]); } int get(int id,int l,int r,int u,int v) { if(l>v||r<u) return 2e9; if(l>=u&&r<=v) return ST[id]; int mid=(l+r)/2; return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v)); } }IT; struct DSU { int lab[N]; void init() { memset(lab,-1,sizeof(lab)); } int root(int u) { if(lab[u]<0) return u; return(lab[u]=root(lab[u])); } bool update(int u,int v) { if((u=root(u))==(v=root(v))) return 0; if(lab[u]>lab[v]) swap(u,v); lab[u]+=lab[v]; lab[v]=u; } }DSU; struct canh { int u,v,w; bool operator<(const canh&A)const { return w<A.w; } }; vector<canh>edge; int get_min(int u,int A,int B) { if(f[u].size()<3) return 2e9; if(A>B) swap(A,B); if(f[u][0]!=A) return f[u][0]; if(f[u][1]!=B) return f[u][1]; return f[u][2]; } void DFS(int u,int p) { cnt[u].fs=++times; sz[u]=1; for(auto v:g[u]) if(v.sc!=p) { cha[v.sc][0]={v.fs,u}; DFS(v.sc,u); sz[u]+=sz[v.sc]; } cnt[u].sc=times; } void hld(int u,int p) { in[u]=chain; pos[u]=++times; if(head[chain]==0) head[chain]=u; for(auto v:g[u]) if(v.sc!=p&&(MV[u]==0||sz[v.sc]>sz[MV[u]])) MV[u]=v.sc; if(MV[u]==0) return; hld(MV[u],u); for(auto v:g[u]) if(v.sc!=p&&v.sc!=MV[u]) { chain++; hld(v.sc,u); } } bool tren(int u,int v) { return(cnt[u].fs<=cnt[v].fs&&cnt[u].sc>=cnt[v].sc); } int lca(int u,int v) { if(tren(u,v)) return u; if(tren(v,u)) return v; for(int k=LOG;k>=0;k--) if(cha[u][k].sc!=0&&!tren(cha[u][k].sc,v)) u=cha[u][k].sc; return cha[u][0].sc; } int con_duoi(int r,int u) { for(int k=LOG;k>=0;k--) if(cha[u][k].sc!=0&&!tren(cha[u][k].sc,r)) u=cha[u][k].sc; return u; } int get_max(int r,int u) { if(r==u) return 0; int res=0; for(int k=LOG;k>=0;k--) if(cha[u][k].sc!=0&&!tren(cha[u][k].sc,r)) { res=max(res,cha[u][k].fs); u=cha[u][k].sc; } return max(res,cha[u][0].fs); } void init(int NNN, int MMM,vector<int> UUU,vector<int> VVV, vector<int> WWW) { while(1); n=NNN; m=MMM; for(int i=0;i<m;i++) { UUU[i]++; VVV[i]++; edge.pb({UUU[i],VVV[i],WWW[i]}); f[UUU[i]].pb(WWW[i]); f[VVV[i]].pb(WWW[i]); } sort(edge.begin(),edge.end()); DSU.init(); for(int i=0;i<m;i++) if(DSU.update(edge[i].u,edge[i].v)) { // cout<<edge[i].u-1<<" "<<edge[i].v-1<<endl; picked[i]=1; g[edge[i].u].pb({edge[i].w,edge[i].v}); g[edge[i].v].pb({edge[i].w,edge[i].u}); } for(int i=1;i<=n;i++) sort(f[i].begin(),f[i].end()); DFS(1,0); times=0; hld(1,0); LOG=log2(n); for(int k=1;k<=LOG;k++) for(int i=1;i<=n;i++) cha[i][k]={max(cha[cha[i][k-1].sc][k-1].fs,cha[i][k-1].fs),cha[cha[i][k-1].sc][k-1].sc}; IT.init(); for(int i=2;i<=n;i++) if(cha[i][0].sc!=1) IT.update(1,1,n,pos[i],get_min(i,cha[i][0].fs,cha[cha[i][0].sc][0].fs)); } int get(int r,int u) { int res=2e9; while(in[u]!=in[r]) { res=min(res,IT.get(1,1,n,pos[head[in[u]]],pos[u])); u=cha[head[in[u]]][0].sc; } if(u==r) return res; return min(res,IT.get(1,1,n,pos[MV[r]],pos[u])); } int get_2_con(int u,int A) { if(f[u].size()<3) return 2e9; if(f[u][0]==A) return max(f[u][1],f[u][2]); if(f[u][1]==A) return max(f[u][0],f[u][2]); return max(f[u][0],f[u][1]); } int getMinimumFuelCapacity(int u, int v) { u++; v++; int r=lca(u,v),res=2e9;///max(get_max(r,u),get_max(r,v)); if(r==u) swap(u,v); if(u!=r) res=min(res,get(r,con_duoi(r,u))); /// cout<<u<<" "<<v<<" "<<r<<" "<<res<<endl; if(v!=r) res=min(res,get(r,con_duoi(r,v))); if(r==v) { res=min(res,get_2_con(r,cha[con_duoi(r,u)][0].fs)); res=min(res,get_2_con(u,cha[u][0].fs)); }else { res=min(res,get_2_con(u,cha[u][0].fs)); res=min(res,get_2_con(v,cha[v][0].fs)); res=min(res,get_min(r,cha[con_duoi(r,u)][0].fs,cha[con_duoi(r,v)][0].fs)); } // cout<<res<<endl; res=max(res,max(get_max(r,u),get_max(r,v))); if(res<2e9) return res; else return -1; } #ifdef SKY int main() { freopen("A.inp","r",stdin); freopen("A.out","w",stdout); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n,m; cin>>n>>m; vector<int>U(m),V(m),W(m); for(int i=0;i<m;i++) cin>>U[i]; for(int i=0;i<m;i++) cin>>V[i]; for(int i=0;i<m;i++) cin>>W[i]; init(n,m,U,V,W); int q; cin>>q; while(q--) { int u,v; cin>>u>>v; cout<<getMinimumFuelCapacity(u,v)<<endl; } return 0; } #endif
#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...