oj.uz

답안 #937396

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
937396 2024-03-04T02:04:07 Z sleepntsheep Rigged Roads (NOI19_riggedroads) C++17
59 / 100
 386 ms 126036 KB 
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

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 600005
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];

void u2(int l,int r,int k){
    l+=N,r+=N+1;
    for(;l<r;l>>=1,r>>=1){
        if(l&1)t2[l]=lo(k,t2[l]),++l;
        if(r&1)--r,t2[r]=lo(t2[r],k);
    }
}

int q2(int p){
    int z=1e8;
    for(p+=N;p;p>>=1)z=lo(z,t2[p]);
    return z;
}

int n,m,h[N],e[N<<1][2],ne=1,y[N],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){
    P[0][u]=p;
        for(int j=1;j<19;++j)P[j][u]=P[j-1][P[j-1][u]];
    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[u]+1;
        ee[v]=j>>1;
        eee[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][v];
    return P[0][u];
}

int anc(int u,int d)
{
    for(int j=19;j--;)if(dd[P[j][u]]>=d)u=P[j][u];
    return 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)
{
    //printf(" SUP %d %d\n",u,a);
    for(;ch[u]!=ch[a];u=P[0][ch[u]])
        upd(0,0,n,ci[ch[u]],ci[u],0),
        u2(ci[ch[u]],ci[u],k);
    upd(0,0,n,ci[a],ci[u],0);
    u2(ci[a],ci[u],k);
}

static int use[N],at[N];

int *eh[N],eo[N];
void append(int i,int j) {
    int o=eo[i]++;
    if(o>=2&&(o&(o-1))==0)eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
    eh[i][o]=j;
}

int main(){
    memset(lz,-1,sizeof lz);
    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;
    dfs(1,1);hld(1,1);

    upd(0,0,n,0,n,1);
    upd(0,0,n,ci[1],ci[1],0);
    u2(0,n,1e8);

    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),uk=anc(u,dd[lca]+1),vk=anc(v,dd[lca]+1);
            //printf(" : %d %d %d %d %d\n",u,v,lca,uk,vk);

            if(u-lca)ord+=cup(u,uk),sup(u,uk,j);
            if(v-lca)ord+=cup(v,vk),sup(v,vk,j);

            use[w[j]=ord++]=1;
        }else {
            if(qry(0,0,n,ci[v],ci[v])){
                use[w[j]=ord++]=1;
                assert(dd[u]+1==dd[v]);
                upd(0,0,n,ci[v],ci[v],0);
            }
        }
    }

    for(int i=0;i<=n+1;++i)eh[i]=(int*)malloc(2*sizeof**eh);
    for(int j=1;j<=m;++j){
        if(!w[j])
        {
            int u=eee[j];
            at[j]=q2(ci[u]);
            if(at[j]>n+1)at[j]=n+1;
            //printf(" : %d %d %d\n",j,u,at[j]);
            append(at[j],j);
        }
    }

    int ord2=1;
    for(int j=0;j<=n+1;++j){
        for(int i=0;i<eo[j];++i){
            while(use[ord2])++ord2;
            w[eh[j][i]]=ord2++;
        }
        //printf(" : %d %d\n",at[ww[j]],ww[j]);
    }

    for(int j=1;j<=m;++j)printf("%d ",w[j]);
}

Compilation message

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

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 80476 KB Output is correct
2 Correct 9 ms 80424 KB Output is correct
3 Correct 10 ms 80476 KB Output is correct

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 80476 KB Output is correct
2 Correct 9 ms 80424 KB Output is correct
3 Correct 10 ms 80476 KB Output is correct
4 Correct 9 ms 80728 KB Output is correct
5 Correct 9 ms 80416 KB Output is correct
6 Correct 10 ms 80476 KB Output is correct
7 Correct 9 ms 80476 KB Output is correct
8 Correct 9 ms 80476 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 88 ms 95568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 106408 KB Output is correct
2 Correct 189 ms 89700 KB Output is correct
3 Correct 103 ms 85328 KB Output is correct
4 Correct 162 ms 100948 KB Output is correct
5 Correct 42 ms 86688 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 118040 KB Output is correct
2 Correct 179 ms 123880 KB Output is correct
3 Correct 52 ms 98792 KB Output is correct
4 Correct 83 ms 104784 KB Output is correct
5 Correct 217 ms 126036 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 112212 KB Output is correct
2 Correct 111 ms 102992 KB Output is correct
3 Correct 386 ms 119904 KB Output is correct
4 Correct 331 ms 115284 KB Output is correct
5 Correct 31 ms 83796 KB Output is correct

Subtask #7
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 80476 KB Output is correct
2 Correct 9 ms 80424 KB Output is correct
3 Correct 10 ms 80476 KB Output is correct
4 Correct 9 ms 80728 KB Output is correct
5 Correct 9 ms 80416 KB Output is correct
6 Correct 10 ms 80476 KB Output is correct
7 Correct 9 ms 80476 KB Output is correct
8 Correct 9 ms 80476 KB Output is correct
9 Incorrect 88 ms 95568 KB Output isn't correct
10 Halted 0 ms 0 KB -