Submission #937298

#TimeUsernameProblemLanguageResultExecution timeMemory
937298sleepntsheepRigged Roads (NOI19_riggedroads)C++17
18 / 100
362 ms75940 KiB
#include<assert.h> #include<stdio.h> #include<set> #include<stdlib.h> #include<string.h> int hi(int a,int b){return a>b?a:b;} unsigned X=12345;int rand_(){return(X*=3)>>1;} int(*compar)(int,int);void sort(int*aa,int l,int r){ while(l<r){ int i=l,j=l,k=r,t,p=aa[l+rand_()%(r-l)]; while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:t=aa[i],aa[i]=aa[j],aa[j]=t,++i,++j;break;case 1:t=aa[--k],aa[k]=aa[j],aa[j]=t;break;}sort(aa,l,i);l=k; }} #define N 300005 int t[N<<2], lz[N<<2]; void push(int v, int l, int r) { if (~lz[v]) { if (l != r) lz[2*v+1] = lz[2*v+2] = lz[v]; t[v] = lz[v]*(r-l+1); lz[v] = -1; } } void upd(int v, int l, int r, int x, int y, int k) { push(v, l, r); if (r < x||y<l)return; if(x<=l&&r<=y){lz[v]=k;push(v,l,r);return;} upd(2*v+1, l,(l+r)/2,x,y,k),upd(2*v+2,(l+r)/2+1,r,x,y,k); t[v]=t[2*v+1]+t[2*v+2]; } int qry(int v,int l,int r,int x,int y) { push(v,l,r); if(r<x||y<l)return 0; if(x<=l&&r<=y)return t[v]; return qry(2*v+1,l,(l+r)/2,x,y)+qry(2*v+2, (l+r)/2+1, r, x,y); } int lo(int a,int b){return a<b?a:b;} int t2[N<<2], lz2[N<<2]; void push2(int v, int l, int r) { if (1e9>lz2[v]) { if (l != r) lz2[2*v+1]=lo(lz2[2*v+1],lz2[v]),lz2[2*v+2]=lo(lz2[2*v+2],lz2[v]), t2[v] = lo(t2[v],lz2[v]); lz2[v] = 1e9; } } void upd2(int v, int l, int r, int x, int y, int k) { push2(v, l, r); if (r < x||y<l)return; if(x<=l&&r<=y){lz2[v]=k;push2(v,l,r);return;} upd2(2*v+1, l,(l+r)/2,x,y,k),upd2(2*v+2,(l+r)/2+1,r,x,y,k); t2[v]=lo(t2[2*v+1],t2[2*v+2]); } int qry2(int v,int l,int r,int x,int y) { push2(v,l,r); if(r<x||y<l)return 1e9; if (x<=l&&r<=y)return t2[v]; return lo(qry2(2*v+1,l,(l+r)/2,x,y),qry2(2*v+2, (l+r)/2+1, r, x,y)); } //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,tune=native") int n,m,h[N],e[N<<1][2],ne=1,y[N],id,P[19][N],dd[N],ch[N],ci[N],timer=0,w[N],ee[N],eee[N],sz[N]; void _l(int u,int v){e[++ne][0]=v,e[ne][1]=h[u],h[u]=ne;} void dfs(int u,int p){ sz[u]=1; for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])!=p&&y[j>>1]){ dd[v]=dd[P[0][v]=u]+1; ee[v]=j>>1; eee[j>>1]=v; for(int j=1;j<19;++j)P[j][v]=P[j-1][P[j-1][v]]; dfs(v,u); sz[u]+=sz[v]; } } void hld(int u,int hh) { int hv=0; for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])!=P[0][u]&&y[j>>1]) if(sz[v]>sz[hv])hv=v; ci[u]=timer++;ch[u]=hh; if(hv)hld(hv,hh); for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])!=P[0][u]&&y[j>>1]&&v-hv) hld(v,v); } int qq(int u,int v){ if(dd[u]>dd[v])return qq(v,u); int dt=dd[v]-dd[u]; for(int j=19;j--;)if(dt&(1<<j))v=P[j][v]; if(u==v)return u; for(int j=19;j--;)if(P[j][u]^P[j][v])u=P[j][u],v=P[j][u]; return P[0][u]; } int need[N],np,ord=1; int cup(int u,int a) { int z=0; for(;ch[u]!=ch[a];u=P[0][ch[u]]) z+=qry(0,0,n,ci[ch[u]],ci[u]); z+=qry(0,0,n,ci[a],ci[u]); return z; } void sup(int u,int a,int k) { for(;ch[u]!=ch[a];u=P[0][ch[u]]) upd(0,0,n,ci[ch[u]],ci[u],0), upd2(0,0,n,ci[ch[u]],ci[u],k); upd(0,0,n,ci[a],ci[u],0); upd2(0,0,n,ci[a],ci[u],k); } int ww[N],wo,at[N]; int c2(int i,int j){ if(at[i]-at[j])return at[i]<at[j]?-1:1; return i<j?-1:i>j?1:0; } static int use[N]; int main(){ memset(lz,-1,sizeof lz); memset(lz2,63,sizeof lz2); memset(t2,63,sizeof t2); scanf("%d%d",&n,&m); for(int u,v,i=1;i<=m;++i)scanf("%d%d",&u,&v),_l(u,v),_l(v,u); for(int j,i=1;i<n;++i)scanf("%d",&j),y[j]=1; P[0][1]=1;dfs(1,1);hld(1,1); upd(0,0,n,0,n,1); upd(0,0,n,ci[1],ci[1],0); upd2(0,0,n,0,n,1e9); for(int j=1;j<=m;++j){ int u=e[j*2][0],v=e[j*2+1][0]; if(dd[v]+1==dd[u]){int t=u;u=v;v=t;} if(!y[j]){ int lca=qq(u,v),tmp=qry(0,0,n,ci[lca],ci[lca]),tmp2=qry(0,0,n,ci[lca],ci[lca]); ord+=cup(u,lca)+ cup(v,lca)-2*qry(0,0,n,ci[lca],ci[lca]); sup(u,lca,j); sup(v,lca,j); upd(0,0,n,ci[lca],ci[lca],tmp); upd2(0,0,n,ci[lca],ci[lca],tmp2); w[j]=ord++; upd(0,0,n,ci[eee[j]],ci[eee[j]],0); }else { if(qry(0,0,n,ci[eee[j]],ci[eee[j]])){ w[j]=ord++; upd(0,0,n,ci[eee[j]],ci[eee[j]],0); } } } for(int u=1;u<=n;++u){ if(ee[u]&&!w[ee[u]]) { at[ee[u]]=qry2(0,0,n,ci[u],ci[u]); assert(at[ee[u]]); ww[wo++]=ee[u]; } } compar=c2;sort(ww,0,wo); for(int i=1;i<=m;++i)use[w[i]]=1; int ord2=1; for(int j=0;j<wo;++j){ while(use[ord2])++ord2; w[ww[j]]=ord2++; } for(int j=1;j<=m;++j)printf("%d ",w[j]); }

Compilation message (stderr)

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:141:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |     for(int u,v,i=1;i<=m;++i)scanf("%d%d",&u,&v),_l(u,v),_l(v,u);
      |                              ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:142:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |     for(int j,i=1;i<n;++i)scanf("%d",&j),y[j]=1;
      |                           ~~~~~^~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...