Submission #937244

#TimeUsernameProblemLanguageResultExecution timeMemory
937244sleepntsheepRigged Roads (NOI19_riggedroads)C++17
0 / 100
2043 ms45904 KiB
#include<stdio.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 #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,tune=native") #define INLINE inline __attribute__((always_inline)) int ttt[N],n,m,h[N],e[N<<1][2],ne=1,y[N],id,pp[N][19],ee[N],dd[N],w[N],tin[N],tout[N],timer=1; void _l(int u,int v){e[++ne][0]=v,e[ne][1]=h[u],h[u]=ne;} void __u(int*t,int p,int k){for(;p<N;p+=p&-p)t[p]+=k; } int __q(int*t,int p){int z=0;for(;p;p-=p&-p)z+=t[p];return z;} int __s(int*t,int k){int p=0,v=0,j=1<<20;for(;j>>=1;)if(p+j<N&&v+t[p+j]<k)v+=t[p+=j];return p+1;} void doedge(int v,int k){ __u(ttt,tin[v],k); __u(ttt,tout[v]+1,-k); } void dfs(int u,int p){ tin[u]=timer++; for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])!=p&&y[j>>1]){ dd[v]=dd[pp[v][0]=u]+1; ee[v]=j>>1; pp[v][0]=u; dfs(v,u); doedge(v,1); } tout[u]=timer-1; } 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=pp[v][j]; if(u==v)return u; for(int j=19;j--;)if(pp[u][j]==pp[v][j])u=pp[u][j],v=pp[v][j]; return pp[u][0]; } int nx(int u,int aa){ if(dd[u]==dd[aa])return u; int base=__q(ttt,tin[u]); for(int j=19;j--;){ if(dd[pp[u][j]]>dd[aa]&&__q(ttt,tin[pp[u][j]])==base)u=pp[u][j]; } return pp[u][0]; } int need[N],np,ord=1; int c1(int i,int j){return i<j?-1:i>j?1:0;} #include<algorithm> int main(){ int sub4=0; 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; pp[1][0]=1;dfs(1,1); for(int j=1;j<19;++j)for(int i=1;i<=n;++i)pp[i][j]=pp[pp[i][j-1]][j-1]; for(int j=1;j<=m;++j)if(!w[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),aa[]={u,v}; for(int kk=0;kk<2;++kk){ int ii=nx(aa[kk],lca); while(dd[ii]>dd[lca]) { doedge(ii,-1),need[np++]=ee[ii]; ii=nx(ii,lca); } } //compar=c1;sort(need,0,np); std::sort(need,need+np); for(int i=0;i<np;++i) w[need[i]]=ord++; np=0; w[j]=ord++; }else{ w[j]=ord++; doedge(v,-1); } } for(int j=1;j<=m;++j)printf("%d ",w[j]); }

Compilation message (stderr)

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:60:9: warning: unused variable 'sub4' [-Wunused-variable]
   60 |     int sub4=0;
      |         ^~~~
riggedroads.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:62:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     for(int u,v,i=1;i<=m;++i)scanf("%d%d",&u,&v),_l(u,v),_l(v,u);
      |                              ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:63:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     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...