Submission #937358

#	Time	Username	Problem	Language	Result	Execution time	Memory
937358		sleepntsheep	Rigged Roads (NOI19_riggedroads)	C++17	58 / 100	2054 ms	37044 KiB

riggedroads

    #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")
     
    int ttt[N],n,m,h[N],e[N<<1][2],ne=1,y[N],id,pp[N],jj[N],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){if(p<1)p=1; for(;p<N;p+=p&-p)t[p]+=k; }
    int __q(int*t,int p){if(p<1)return 0;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]=u]+1;
            ee[v]=j>>1;
            pp[v]=u;
            jj[v]=(dd[p]-dd[jj[u]]==dd[jj[u]]-dd[jj[jj[u]]])?jj[jj[u]]: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);
        while(dd[v]>dd[u])
            if(dd[jj[v]]>=dd[u]) v=jj[v];
            else v=pp[v];
        while(u-v)
            if(jj[v]-jj[u])u=jj[u],v=jj[v];
            else u=pp[u],v=pp[v];
        return u;
    }
     
    int nx(int u,int aa){
        int base=__q(ttt,tin[u]);
        while(dd[u]>dd[aa]&&__q(ttt,tin[pp[u]])==base){
            u=(dd[jj[u]]>dd[aa]&&__q(ttt,tin[jj[u]])==base)?jj[u]:pp[u];
        }
        return u;
    }
     
    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]=jj[1]=1;dfs(1,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:61:13: warning: unused variable 'sub4' [-Wunused-variable]
   61 |         int sub4=0;
      |             ^~~~
riggedroads.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:63:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         for(int u,v,i=1;i<=m;++i)scanf("%d%d",&u,&v),_l(u,v),_l(v,u);
      |                                  ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:64:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         for(int j,i=1;i<n;++i)scanf("%d",&j),y[j]=1;
      |                               ~~~~~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 0 / 32