oj.uz

Submission #937215

# Submission time Handle Problem Language Result Execution time Memory
937215 2024-03-03T16:15:05 Z sleepntsheep Rigged Roads (NOI19_riggedroads) C++17
58 / 100
 2000 ms 36640 KB 
#include<stdio.h>
#include<assert.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 ttt[N],n,m,h[N],e[N<<1][2],ne,y[N],id,pp[N],jj[N],ee[N],dd[N],w[N],tin[N],tout[N],timer;
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);
}

int vs[N];
void dfs(int u,int p){
    if(vs[u])assert(0);
    tin[u]=timer++;
    vs[u]=1;
    for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])!=p&&y[(j+1)/2]){
        if(vs[v])continue;
        dd[v]=dd[pp[v]=u]+1;
        ee[v]=(j+1)/2;
        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;

int c1(int i,int j){return ee[i]<ee[j]?-1:ee[i]>ee[j]?1:0;}

int main(){
    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);

    int ord = 1;
    for(int j=1;j<=m;++j){
        int u=e[j*2-1][0],v=e[j*2][0];
        if(dd[v]+1==dd[u]){int t=u;u=v;v=t;}
        if(w[j])continue;
        if(!y[j]){
            int lca=qq(u,v);
            for(int ii=nx(u,lca);dd[ii]>dd[lca];ii=nx(ii,lca)) doedge(ii,-1),need[np++]=ii;
            for(int ii=nx(v,lca);dd[ii]>dd[lca];ii=nx(ii,lca)) doedge(ii,-1),need[np++]=ii;
            compar=c1;sort(need,0,np);
            for(int i=0;i<np;++i) w[ee[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

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:64:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     for(int u,v,i=1;i<=m;++i)scanf("%d%d",&u,&v),_l(u,v),_l(v,u);
      |                              ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:65:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     for(int j,i=1;i<n;++i)scanf("%d",&j),y[j]=1;
      |                           ~~~~~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6504 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6504 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6720 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 10840 KB Output is correct
2 Correct 93 ms 14324 KB Output is correct
3 Correct 81 ms 16680 KB Output is correct
4 Correct 112 ms 22748 KB Output is correct
5 Correct 114 ms 23888 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2015 ms 19304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 26736 KB Output is correct
2 Correct 127 ms 36640 KB Output is correct
3 Correct 40 ms 14932 KB Output is correct
4 Correct 46 ms 20732 KB Output is correct
5 Correct 146 ms 36184 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 22860 KB Output is correct
2 Correct 54 ms 18772 KB Output is correct
3 Correct 149 ms 31668 KB Output is correct
4 Correct 185 ms 29212 KB Output is correct
5 Correct 12 ms 8284 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6504 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6720 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 37 ms 10840 KB Output is correct
10 Correct 93 ms 14324 KB Output is correct
11 Correct 81 ms 16680 KB Output is correct
12 Correct 112 ms 22748 KB Output is correct
13 Correct 114 ms 23888 KB Output is correct
14 Execution timed out 2015 ms 19304 KB Time limit exceeded
15 Halted 0 ms 0 KB -