oj.uz

Submission #941100

# Submission time Handle Problem Language Result Execution time Memory
941100 2024-03-08T07:11:49 Z sleepntsheep Transport (COCI19_transport) C
26 / 130
 530 ms 65536 KB 
#include<stdio.h>

#define M 2000000
long long _t[M],_l[M],_r[M],_al=1;

void _p(int v,long long l,long long r)
{
    if(!_l[v])
    {
        _l[v]=++_al;
        _r[v]=++_al;
    }
}

void _u(int v,long long l, long long r,long long p,int k)
{
    if(l==r)
    {
        _t[v]+=k;
        return;
    }
    _p(v,l,r);
    if(p<=(l+r)/2)
        _u(_l[v],l,(l+r)/2,p,k);
    else _u(_r[v],(l+r)/2+1,r,p,k);
    _t[v]=_t[_l[v]]+_t[_r[v]];
}

int _q(int v,long long l,long long r,long long x,long long y)
{
    if(r<x||y<l)return 0;
    if(x<=l&&r<=y)return _t[v];
    _p(v,l,r);
    return (_l[v]?_q(_l[v],l,(l+r)/2,x,y):0)
        + (_r[v]?_q(_r[v],(l+r)/2+1,r,x,y):0);
}

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[200000][3],ne,h[100001],ded[100001],sz[100001];
long long ll[100001],mm[100001],ll2[100001],mm2[100001];
long long 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)
{
    //printf(" :(%d) %lld %lld %lld %lld\n",u,ll[u],mm[u],ll2[u],mm2[u]);
    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);
    }
}

void dfs3(int u,int p,int k)
{
    if(mm[u]>=0)
    {
        _u(1,0,1e18,ll[u],k);
        if(k==1)++z;
    }
    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;
        z+=_t[1];
    }
    else
    {
        z+=_q(1,0,1e18,-mm2[u],1e18);
    }
    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;

    //printf(" DECOMP %d\n",u);

    long long z0=z;

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

    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);
    }

    //printf(" %d (Z: %lld\n",u,z-z0);

    for(int j=h[u];j;j=e[j][2])if(!ded[e[j][0]])
        decomp(e[j][0]);
}

#define _assert(x) if(!(x)) __builtin_trap();

int main(){
    _u(1,0,1e18,4,1);
    _assert(_q(1,0,1e18,5,1e18)==0);
    _assert(_q(1,0,1e18,4,1e18)==1);
    _u(1,0,1e18,4,-1);
    _assert(_q(1,0,1e18,4,1e18)==0);
    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 'decomp':
transport.c:101:15: warning: unused variable 'z0' [-Wunused-variable]
  101 |     long long z0=z;
      |               ^~
transport.c: In function 'main':
transport.c:132:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     scanf("%d",&n);
      |     ^~~~~~~~~~~~~~
transport.c:133:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     for(int i=1;i<=n;++i)scanf("%d",a+i);
      |                          ^~~~~~~~~~~~~~~
transport.c:135:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10320 KB Output is correct
2 Correct 21 ms 12760 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 22096 KB Output is correct
2 Correct 48 ms 15636 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 247 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 333 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 267 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 332 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 42712 KB Output is correct
2 Runtime error 506 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 479 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 530 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 499 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -