oj.uz

답안 #941121

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941121 2024-03-08T07:27:47 Z sleepntsheep Transport (COCI19_transport) C
130 / 130
 413 ms 15952 KB 
#include<stdio.h>

unsigned X=12345;int rand_(){return(X*=3)>>1;}
void sort(long long*aa,int l,int r)
{
    while(l<r)
    {
        int i=l,j=l,k=r;
        long long t,p=aa[l+rand_()%(r-l)];
        while(j<k)
            if(aa[j]<p)
                t=aa[i],aa[i]=aa[j],aa[j]=t,++i,++j;
            else if(aa[j]==p)
                ++j;
            else
                t=aa[--k],aa[k]=aa[j],aa[j]=t;
        sort(aa,l,i);
        l=k;
    }
}

int t[1<<19];

void _u(int p,int k) { for(;p;p-=p&-p)t[p]+=k; }

int _q(int p) { int z=0; for(;p<sizeof t/sizeof*t;p+=p&-p)z+=t[p]; return z; }

long long cc[1<<19];
int co;

int lb(long long x)
{
    int l=0,r=co-1;
    while(l<=r)
    {
        int m=(l+r)/2;
        if(cc[m]>=x)r=m-1;
        else l=m+1;
    }
    return r+1+1;
}

long long hi(long long a,long long b) { return a>b?a:b; }
long long lo(long long a,long long b) { return a<b?a:b; }

int n,a[100001],e[200002][3],ne,h[100001],ded[100001],sz[100001];
long long ll[100001],mm[100001],ll2[100001],mm2[100001],z;

void dfs(int u,int p)
{
    sz[u]=1;for(int j=h[u];j;j=e[j][2])if(e[j][0]-p&&!ded[e[j][0]])dfs(e[j][0],u),sz[u]+=sz[e[j][0]];
}

int cen(int u,int p,int tn)
{
    for(int j=h[u];j;j=e[j][2])if(e[j][0]-p&&!ded[e[j][0]]&&sz[e[j][0]]*2>=tn)return cen(e[j][0],u,tn);
    return u;
}

void dfs2(int u,int p)
{
    for(int j=h[u];j;j=e[j][2])if(e[j][0]-p&&!ded[e[j][0]])
    {
        ll[e[j][0]]=a[e[j][0]]-e[j][1]+ll[u];
        mm[e[j][0]]=lo(mm[u],0)+(a[e[j][0]]-e[j][1]);
        ll2[e[j][0]]=ll2[u]+a[u]-e[j][1];
        mm2[e[j][0]]=lo(mm2[u],ll2[e[j][0]]);
        dfs2(e[j][0],u);
    }
    cc[co++]=ll[u];
    cc[co++]=mm2[u];
}

void dfs3(int u,int p,int k)
{
    if(mm[u]>=0) _u(lb(ll[u]),k), z+=(k==1);
    for(int j=h[u];j;j=e[j][2])if(e[j][0]-p&&!ded[e[j][0]])dfs3(e[j][0],u,k);
}

void dfs4(int u,int p,int k)
{
    if(mm2[u]>=0) z+=k+_q(1);
    else z+=_q(lb(-mm2[u]));
    for(int j=h[u];j;j=e[j][2])if(e[j][0]-p&&!ded[e[j][0]])dfs4(e[j][0],u,k);
}

void decomp(int u)
{
    dfs(u,-1);
    u=cen(u,-1,sz[u]);
    ded[u]=1;

    co=ll[u]=mm[u]=ll2[u]=mm2[u]=0;
    dfs2(u,-1);
    sort(cc,0,co);

    for(int j=h[u];j;j=e[j][2])if(!ded[e[j][0]]) dfs4(e[j][0],u,1), dfs3(e[j][0],u,1);
    for(int j=h[u];j;j=e[j][2])if(!ded[e[j][0]]) dfs3(e[j][0],u,-1), dfs4(e[j][0],u,0);
    for(int j=h[u];j;j=e[j][2])if(!ded[e[j][0]]) decomp(e[j][0]);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    for(int i=1,u,v,w;i<n;++i)
        scanf("%d%d%d",&u,&v,&w),e[++ne][0]=v,e[ne][1]=w,e[ne][2]=h[u],h[u]=ne,e[++ne][0]=u,e[ne][1]=w,e[ne][2]=h[v],h[v]=ne;
    decomp(1);
    printf("%lld",z);
}

Compilation message

transport.c: In function 'main':
transport.c:103:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf("%d",&n);
      |     ^~~~~~~~~~~~~~
transport.c:104:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     for(int i=1;i<=n;++i)scanf("%d",a+i);
      |                          ^~~~~~~~~~~~~~~
transport.c:106:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         scanf("%d%d%d",&u,&v,&w),e[++ne][0]=v,e[ne][1]=w,e[ne][2]=h[u],h[u]=ne,e[++ne][0]=u,e[ne][1]=w,e[ne][2]=h[v],h[v]=ne;
      |         ^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4700 KB Output is correct
2 Correct 7 ms 4700 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4988 KB Output is correct
2 Correct 13 ms 5124 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 11532 KB Output is correct
2 Correct 118 ms 11300 KB Output is correct

Subtask #4
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 13136 KB Output is correct
2 Correct 204 ms 13312 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 14924 KB Output is correct
2 Correct 333 ms 15952 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 8020 KB Output is correct
2 Correct 47 ms 7768 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 8784 KB Output is correct
2 Correct 169 ms 8756 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 9580 KB Output is correct
2 Correct 193 ms 9252 KB Output is correct

Subtask #9
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 9812 KB Output is correct
2 Correct 281 ms 9932 KB Output is correct

Subtask #10
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 413 ms 10884 KB Output is correct
2 Correct 379 ms 10128 KB Output is correct