Submission #944100

#	Time	Username	Problem	Language	Result	Execution time	Memory
944100		sleepntsheep	Dynamic Diameter (CEOI19_diameter)	C11	100 / 100	4544 ms	130828 KiB

diameter

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

inline long long maxll(long long a,long long b){return a>b?a:b;}
#include<stdio.h>
#include<stdlib.h>
#define N 100005

/* RNG */
unsigned X=12345; int rand_(){return(X*=3)>>1;}

/* SORT */
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;
    }
}

int compar_1(int i,int j){return i<j?-1:i>j?1:0;}

/* TREAP MULTISET */


#define M 500000
long long _A[M];
int _B[M],_L[M],_R[M],_K[M],_talc,_trash[M],_to;

void _treap_print_(int v)
{
    if(!v)return;
    _treap_print_(_L[v]);
    printf(" (%lld %d)",_A[v],_K[v]);
    _treap_print_(_R[v]);
}

void _treap_print(int v)
{
    return;
    _treap_print_(v);
    puts("");
}

int _treap_new(long long x)
{
    int p=_to?_trash[--_to]:++_talc;
    _A[p]=x;
    _B[p]=rand_();
    _L[p]=_R[p]=0;
    _K[p]=1;
    return p;
}

void _split(int v,int*l,int*r,long long k)
{
    if(!v){*l=*r=0;return;}
    if(_A[v]<=k)
        _split(_R[v],&_R[v],r,k), *l=v;
    else
        _split(_L[v],l,&_L[v],k), *r=v;
}

void _merge(int*v,int l,int r)
{
    if(!l||!r){*v=l^r;return;}
    if(_B[l]<_B[r])
        _merge(&_L[r],l,_L[r]), *v=r;
    else
        _merge(&_R[l],_R[l],r), *v=l;
}

void _insert(int*v,long long k)
{
    //puts("INSERT");
    int t1,t2,t3,t4,t5;
    _split(*v,&t5,&t3,k);
    _split(t5,&t1,&t2,k-1);
    //puts("S1"); _treap_print(t1); _treap_print(t2); _treap_print(t3);
    if(!t2) t2 = _treap_new(k);
    else ++_K[t2];
    //_treap_print(t1); _treap_print(t2); _treap_print(t3);
    _merge(&t4,t1,t2);
    _merge(v,t4,t3);
}

void _delete(int*v,long long k)
{
    int t1,t2,t3;
    _split(*v,&t2,&t3,k);
    _split(t2,&t1,&t2,k-1);
    if(!t2) ;
    else 
    {
        if(_K[t2] > 1)--_K[t2];
        else _trash[_to++]=t2,t2=0;
    }
    _merge(&t2,t1,t2);
    _merge(v,t2,t3);
}

long long _sum_high2(int*v)
{
    if(!*v)return 0;

    int u=*v;
    long long apar=0;
    while(_R[u])apar=_A[u],u=_R[u];
    if(_K[u]>1)return 2*_A[u];

    long long one=_A[u];

    if(_L[u])
    {
        u=_L[u];
        while(_R[u])u=_R[u];
        return _A[u]+one;
    }
    return one+apar;
}

/* RANGE_ADDITION UPDATE, RANGE MAX QUERY SEGMENT TREE */
typedef struct
{
    long long*t,*lz;
    int ll,rr;
} S;

void S_init(S*s,int ll,int rr)
{
    s->ll=ll;
    s->rr=rr;
    int n=rr-ll+1;
    while(n&n-1)++n;
    n=n<<1;
    s->t=(long long*)calloc(n,sizeof*s->t);
    s->lz=(long long*)calloc(n,sizeof*s->lz);
}

void _S_push(S*s,int v,int l,int r)
{
    if(s->lz[v])
    {
        s->t[v] += s->lz[v];
        if(l^r)
        {
            s->lz[2*v+1]+=s->lz[v];
            s->lz[2*v+2]+=s->lz[v];
        }
        s->lz[v]=0;
    }
}

void _S_add(S*s,int v,int l,int r,int x,int y,long long k)
{
    _S_push(s,v,l,r);
    if(r<x||y<l)return;
    if(x<=l&&r<=y)
    {
        s->lz[v]=k;
        _S_push(s,v,l,r);
        return;
    }
    _S_add(s,2*v+1,l,(l+r)/2,x,y,k);
    _S_add(s,2*v+2,(l+r)/2+1,r,x,y,k);
    s->t[v]=maxll(s->t[2*v+1],s->t[2*v+2]);
}

void S_add(S*s,int x,int y,long long k) { _S_add(s,0,s->ll,s->rr,x,y,k); }
long long _S_qry(S*s,int v,int l,int r,int x,int y)
{
    _S_push(s,v,l,r);
    if(r<x||y<l)return -1;
    if(x<=l&&r<=y)return s->t[v];
    return maxll(_S_qry(s,2*v+1,l,(l+r)/2,x,y),_S_qry(s,2*v+2,(l+r)/2+1,r,x,y));
}
long long S_qry(S*s,int x,int y) { return _S_qry(s,0,s->ll,s->rr,x,y); }


int n, q;
long long W;

typedef struct { int v, l; long long w; } edge;

edge e[N<<1];
int eo,h[N];


void link(int u,int v,long long w)
{
    ++eo;
    e[eo].v=v;e[eo].w=w;e[eo].l=h[u];h[u]=eo;
}

int sz[N],ded[N],cenpar[N],in[N],csz[N],*ccrd[N],clb[N],*tin[N],*tout[N],edge_appear[N];
int *children[N],co[N];
S seg[N];
int multiset[N];

int lb(int cen,int x)
{
    int o,l=0,r=csz[cen]-1;
    while(l<=r)
    {
        o=(l+r)/2;
        if(ccrd[cen][o]>=x)r=o-1;
        else l=o+1;
    }
    return r+1;
}

void dfs0(int u,int p)
{
    sz[u]=1;
    for(int v,j=h[u];j;j=e[j].l)if((v=e[j].v)!=p&&!ded[v]) dfs0(v,u), sz[u]+=sz[v];
}

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

int dfs1(int u,int p)
{
    int zz=1;
    for(int j=h[u];j;j=e[j].l)if(e[j].v!=p&&!ded[e[j].v])zz+=dfs1(e[j].v,u);
    return zz;
}

int dfs2_o=0;
void dfs2(int cen,int u,int p)
{
    ccrd[cen][dfs2_o++]=u;
    for(int j=h[u];j;j=e[j].l)if(e[j].v!=p&&!ded[e[j].v])dfs2(cen,e[j].v,u);
}

void dfs3(int cen,int u,int p)
{
    clb[u]=lb(cen,u);
    for(int j=h[u];j;j=e[j].l)if(e[j].v!=p&&!ded[e[j].v])dfs3(cen,e[j].v,u);
}

int dfs4_timer=0;
void dfs4(int cen,int u,int p)
{
    tin[cen][clb[u]]=dfs4_timer++;
    for(int v,j=h[u];j;j=e[j].l)if((v=e[j].v)!=p&&!ded[e[j].v]){
        edge_appear[(j+1)/2]=cen;
        dfs4(cen,v,u);
    }
    tout[cen][clb[u]]=dfs4_timer-1;
}

void dfs5(int cen,int u,int p)
{
    for(int v,j=h[u];j;j=e[j].l)if((v=e[j].v)!=p&&!ded[e[j].v]){
        //printf(" On cen %d and go %d [%d %d] adding %lld\n",cen,v,tin[cen][clb[v]],tout[cen][clb[v]],e[j].w);
        S_add(seg+cen,tin[cen][clb[v]],tout[cen][clb[v]],e[j].w);
        dfs5(cen,v,u);
    }
}

long long deep(int cen,int lbch)
{
    return S_qry(seg+cen,tin[cen][lbch],tout[cen][lbch]);
}

void dfsdebug(int cen,int u,int p)
{
    //printf(" %d: %lld\n",u,deep(cen,lb(cen,u)));
    for(int v,j=h[u];j;j=e[j].l)if((v=e[j].v)!=p&&!ded[e[j].v]){
        //printf(" On cen %d and go %d [%d %d] adding %lld\n",cen,v,tin[cen][clb[v]],tout[cen][clb[v]],e[j].w);
        //S_add(seg+cen,tin[cen][clb[v]],tout[cen][clb[v]],e[j].w);
        dfsdebug(cen,v,u);
    }
}


int focused_centroid;
int compar_2(int i,int j)
{
    int szi=tin[focused_centroid][i];
    int szj=tin[focused_centroid][j];
    return szi<szj?-1:szi>szj?1:0;
}


/* multiset storing answer for each centroid */
int diameter;

int decomp(int u)
{
    dfs0(u,-1);
    u=cen(u,-1,sz[u]);

    focused_centroid = u;

    ded[u]=1;

    /* dfs sz */
    csz[u]=dfs1(u,-1);

    /* allocate memory for cordinate compression , then do it */
    ccrd[u]=(int*)malloc(csz[u]*sizeof**ccrd);
    dfs2_o=0; dfs2(u,u,-1);
    compar=compar_1;sort(ccrd[u],0,csz[u]);

    /* initialize segtree */
    S_init(seg+u,0,csz[u]);

    /* calculate clb[v] for all v in sub u */
    dfs3(u,u,-1);

    /* euler tour */
    tin[u]=(int*)malloc(csz[u]*sizeof**tin);
    tout[u]=(int*)malloc(csz[u]*sizeof**tout);
    dfs4_timer=0;
    dfs4(u,u,-1);

    /* add initial edge weights */
    dfs5(u,u,-1);
    //dfsdebug(u,u,-1);

    /* create multiset of centroid's children with D[v]+w[v] */
    multiset[u]=0;
    int oooo=0;
    for(int j=h[u];j;j=e[j].l)if(!ded[e[j].v])
    {
        //printf(" ON %d: child %d with weight %lld + %lld\n",u,e[j].v,e[j].w,S_qry(seg+u,tin[u][clb[e[j].v]],tout[u][clb[e[j].v]]));
        if(deep(u,clb[e[j].v])==3382)
        {
            //printf(" EEEEEEE: %d %d\n",u,e[j].v);
        }
        _insert(multiset+u,deep(u,clb[e[j].v]));
        ++co[u];
    }

    /* store childrens and sort them by discovery time */
    children[u]=(int*)malloc(sizeof**children*co[u]);

    for(int j=h[u];j;j=e[j].l)if(!ded[e[j].v])children[u][oooo]=clb[e[j].v],++oooo;

    compar=compar_2;
    sort(children[u],0,co[u]);

    /* */
    //printf(" Of %d : %lld\n",u,_sum_high2(multiset+u));
    //_treap_print(multiset[u]);
    //puts("EEE"); _treap_print(multiset[u]); printf(" : %lld\n",_sum_high2(multiset+u));

    _insert(&diameter,_sum_high2(multiset+u));

    //printf(" MS %d : ",u); _treap_print(multiset[u]); _treap_print(diameter);

    /* decomp on children */
    for(int v,j=h[u];j;j=e[j].l)if(!ded[v=e[j].v]){
        int vcen = decomp(v);
        in[(j+1)/2]=u;
        cenpar[vcen]=u;
    }

    return u;
}

/* return the lowest node between 2 node connected by edge j; j in [1..n-1] */
int edge_lower(int cen,int j)
{
    int u=e[j*2].v,v=e[j*2-1].v;
    if(tin[cen][lb(cen,u)]>tin[cen][lb(cen,v)])return u;
    return v;
}

/* return order of v - direct children of centroid such that node (lbu) is contained in subtree of v
 * */
int children_containing(int cen,int lbu)
{
    int o,l=0,r=co[cen]-1,z=-1;
    while(l<=r)
    {
        o=(l+r)/2;
        if(tin[cen][children[cen][o]]>tin[cen][lbu])r=o-1,z=children[cen][o];
        else l=o+1;
    }
    return children[cen][l-1];
}

void update_edge(int j,long long nw)
{
    long long old=e[j*2-1].w;
    long long delta = nw - e[j*2-1].w;
    int cen = edge_appear[j];
    //printf(" DELTA: %lld\n",delta);
    while(cen)
    {
        _delete(&diameter,_sum_high2(multiset+cen));
        int lower=edge_lower(cen,j);
        int lblower=lb(cen,lower);

        int child=children_containing(cen,lblower);

        //printf(" UPDATING FOR %d, lblower = %d EDGE IS IN CHILD %d\n",cen,lower,ccrd[cen][child]);


        if (child==lblower)
        {
            _delete(multiset+cen,deep(cen,child));
            S_add(seg+cen,tin[cen][lblower],tout[cen][lblower],delta);
            //children_w[cen][childo]=nw;
            _insert(multiset+cen,deep(cen,child));
        }
        else
        {
            _delete(multiset+cen,deep(cen,child));
            S_add(seg+cen,tin[cen][lblower],tout[cen][lblower],delta);
            _insert(multiset+cen,deep(cen,child));
        }

        _insert(&diameter,_sum_high2(multiset+cen));

        //printf("UPDATED FOR %d, GOING TO %d\n",cen,cenpar[cen]);_treap_print(multiset[cen]);
        cen=cenpar[cen];
    }

    e[j*2-1].w = e[j*2].w = nw;
}

long long last_ans=0;

#define ASSERT(x) if (!(x)) __builtin_trap()

void test()
{
    int t1=_treap_new(2);

    _insert(&t1,2);
    _insert(&t1,1);
    _insert(&t1,3);

    _delete(&t1,1);
    _delete(&t1,2);
    _delete(&t1,3);


    _insert(&t1,1);
    ASSERT(_sum_high2(&t1)==3);

    _delete(&t1,1);
    ASSERT(_sum_high2(&t1)==2);
    _delete(&t1,2);
    ASSERT(_sum_high2(&t1)==0);
    ASSERT(_A[t1]==0);
    ASSERT(t1==0);

    _insert(&t1,2);
    _insert(&t1,3);
    _insert(&t1,1);
    ASSERT(_sum_high2(&t1)==5);
 
    t1=0;

    S s;
    S_init(&s,0,3);
    S_add(&s,1,1,1000);
    ASSERT(S_qry(&s,1,1)==1000);
    ASSERT(S_qry(&s,2,3)==0);

    ASSERT(S_qry(&s,1,3)==1000);
    S_add(&s,1,1,-1000);
    ASSERT(S_qry(&s,1,1)==0);
    ASSERT(S_qry(&s,1,3)==0);


    fputs("DONE TESTING\n",stderr);
}


long long answer()
{
    int uu=diameter;
    while (_R[uu])uu=_R[uu];
    return _A[uu];
}

int main()
{
    test();

    scanf("%d%d%lld",&n,&q,&W);
    for(long long u,v,w,i=1;i<n;++i)
        scanf("%lld%lld%lld",&u,&v,&w),link(u,v,w),link(v,u,w);

    decomp(1);



    //printf("%lld\n",answer());
    for(long long id,nw;q--;)
    {
        scanf("%lld%lld",&id,&nw);
        id = (id + last_ans) % (n-1);
        nw = (nw + last_ans) % W;

        update_edge(id+1,nw);
        int uu=diameter;
        while (_R[uu])uu=_R[uu];
        printf("%lld\n",last_ans=_A[uu]);
    }

}

Compilation message (stderr)

diameter.c: In function 'S_init':
diameter.c:150:14: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  150 |     while(n&n-1)++n;
      |             ~^~
diameter.c: In function 'children_containing':
diameter.c:394:27: warning: variable 'z' set but not used [-Wunused-but-set-variable]
  394 |     int o,l=0,r=co[cen]-1,z=-1;
      |                           ^
diameter.c: In function 'update_edge':
diameter.c:406:15: warning: unused variable 'old' [-Wunused-variable]
  406 |     long long old=e[j*2-1].w;
      |               ^~~
diameter.c: In function 'main':
diameter.c:505:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  505 |     scanf("%d%d%lld",&n,&q,&W);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.c:507:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  507 |         scanf("%lld%lld%lld",&u,&v,&w),link(u,v,w),link(v,u,w);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.c:516:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  516 |         scanf("%lld%lld",&id,&nw);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27