oj.uz

Submission #944100

# Submission time Handle Problem Language Result Execution time Memory
944100 2024-03-12T08:28:49 Z sleepntsheep Dynamic Diameter (CEOI19_diameter) C
100 / 100
 4544 ms 130828 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14840 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14796 KB Output is correct
7 Correct 2 ms 14680 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14876 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 2 ms 14796 KB Output is correct
16 Correct 2 ms 14684 KB Output is correct
17 Correct 2 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14840 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14796 KB Output is correct
7 Correct 2 ms 14680 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14876 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 2 ms 14796 KB Output is correct
16 Correct 2 ms 14684 KB Output is correct
17 Correct 2 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 28 ms 15448 KB Output is correct
20 Correct 34 ms 15500 KB Output is correct
21 Correct 35 ms 15532 KB Output is correct
22 Correct 40 ms 15588 KB Output is correct
23 Correct 49 ms 18104 KB Output is correct
24 Correct 67 ms 18780 KB Output is correct
25 Correct 73 ms 19028 KB Output is correct
26 Correct 83 ms 20048 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 17 ms 14940 KB Output is correct
5 Correct 64 ms 15528 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 14940 KB Output is correct
9 Correct 7 ms 14940 KB Output is correct
10 Correct 22 ms 15196 KB Output is correct
11 Correct 120 ms 16068 KB Output is correct
12 Correct 8 ms 16476 KB Output is correct
13 Correct 8 ms 16476 KB Output is correct
14 Correct 11 ms 16732 KB Output is correct
15 Correct 34 ms 16936 KB Output is correct
16 Correct 133 ms 17872 KB Output is correct
17 Correct 131 ms 48808 KB Output is correct
18 Correct 133 ms 48976 KB Output is correct
19 Correct 140 ms 48936 KB Output is correct
20 Correct 169 ms 49492 KB Output is correct
21 Correct 336 ms 50380 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15452 KB Output is correct
2 Correct 42 ms 15576 KB Output is correct
3 Correct 201 ms 16156 KB Output is correct
4 Correct 381 ms 16708 KB Output is correct
5 Correct 43 ms 22608 KB Output is correct
6 Correct 112 ms 22760 KB Output is correct
7 Correct 371 ms 23372 KB Output is correct
8 Correct 690 ms 24096 KB Output is correct
9 Correct 231 ms 58192 KB Output is correct
10 Correct 324 ms 58456 KB Output is correct
11 Correct 785 ms 59212 KB Output is correct
12 Correct 1302 ms 59868 KB Output is correct
13 Correct 496 ms 105552 KB Output is correct
14 Correct 620 ms 105768 KB Output is correct
15 Correct 1191 ms 106236 KB Output is correct
16 Correct 1822 ms 107092 KB Output is correct
17 Correct 3175 ms 106636 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2920 ms 99556 KB Output is correct
2 Correct 3223 ms 101904 KB Output is correct
3 Correct 3016 ms 104592 KB Output is correct
4 Correct 3090 ms 106328 KB Output is correct
5 Correct 3029 ms 102584 KB Output is correct
6 Correct 2542 ms 83108 KB Output is correct
7 Correct 4182 ms 123852 KB Output is correct
8 Correct 4219 ms 123696 KB Output is correct
9 Correct 4321 ms 123908 KB Output is correct
10 Correct 4134 ms 123192 KB Output is correct
11 Correct 4014 ms 118320 KB Output is correct
12 Correct 3434 ms 93588 KB Output is correct
13 Correct 4299 ms 130216 KB Output is correct
14 Correct 4544 ms 130616 KB Output is correct
15 Correct 4276 ms 130348 KB Output is correct
16 Correct 4374 ms 130260 KB Output is correct
17 Correct 4243 ms 124736 KB Output is correct
18 Correct 3531 ms 97388 KB Output is correct
19 Correct 4396 ms 130320 KB Output is correct
20 Correct 4311 ms 130828 KB Output is correct
21 Correct 4333 ms 130508 KB Output is correct
22 Correct 4296 ms 130048 KB Output is correct
23 Correct 4094 ms 125420 KB Output is correct
24 Correct 3394 ms 97488 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14840 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14796 KB Output is correct
7 Correct 2 ms 14680 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14876 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 2 ms 14796 KB Output is correct
16 Correct 2 ms 14684 KB Output is correct
17 Correct 2 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 28 ms 15448 KB Output is correct
20 Correct 34 ms 15500 KB Output is correct
21 Correct 35 ms 15532 KB Output is correct
22 Correct 40 ms 15588 KB Output is correct
23 Correct 49 ms 18104 KB Output is correct
24 Correct 67 ms 18780 KB Output is correct
25 Correct 73 ms 19028 KB Output is correct
26 Correct 83 ms 20048 KB Output is correct
27 Correct 2 ms 14680 KB Output is correct
28 Correct 2 ms 14684 KB Output is correct
29 Correct 3 ms 14936 KB Output is correct
30 Correct 17 ms 14940 KB Output is correct
31 Correct 64 ms 15528 KB Output is correct
32 Correct 2 ms 14684 KB Output is correct
33 Correct 2 ms 14940 KB Output is correct
34 Correct 2 ms 14940 KB Output is correct
35 Correct 7 ms 14940 KB Output is correct
36 Correct 22 ms 15196 KB Output is correct
37 Correct 120 ms 16068 KB Output is correct
38 Correct 8 ms 16476 KB Output is correct
39 Correct 8 ms 16476 KB Output is correct
40 Correct 11 ms 16732 KB Output is correct
41 Correct 34 ms 16936 KB Output is correct
42 Correct 133 ms 17872 KB Output is correct
43 Correct 131 ms 48808 KB Output is correct
44 Correct 133 ms 48976 KB Output is correct
45 Correct 140 ms 48936 KB Output is correct
46 Correct 169 ms 49492 KB Output is correct
47 Correct 336 ms 50380 KB Output is correct
48 Correct 8 ms 15452 KB Output is correct
49 Correct 42 ms 15576 KB Output is correct
50 Correct 201 ms 16156 KB Output is correct
51 Correct 381 ms 16708 KB Output is correct
52 Correct 43 ms 22608 KB Output is correct
53 Correct 112 ms 22760 KB Output is correct
54 Correct 371 ms 23372 KB Output is correct
55 Correct 690 ms 24096 KB Output is correct
56 Correct 231 ms 58192 KB Output is correct
57 Correct 324 ms 58456 KB Output is correct
58 Correct 785 ms 59212 KB Output is correct
59 Correct 1302 ms 59868 KB Output is correct
60 Correct 496 ms 105552 KB Output is correct
61 Correct 620 ms 105768 KB Output is correct
62 Correct 1191 ms 106236 KB Output is correct
63 Correct 1822 ms 107092 KB Output is correct
64 Correct 3175 ms 106636 KB Output is correct
65 Correct 2920 ms 99556 KB Output is correct
66 Correct 3223 ms 101904 KB Output is correct
67 Correct 3016 ms 104592 KB Output is correct
68 Correct 3090 ms 106328 KB Output is correct
69 Correct 3029 ms 102584 KB Output is correct
70 Correct 2542 ms 83108 KB Output is correct
71 Correct 4182 ms 123852 KB Output is correct
72 Correct 4219 ms 123696 KB Output is correct
73 Correct 4321 ms 123908 KB Output is correct
74 Correct 4134 ms 123192 KB Output is correct
75 Correct 4014 ms 118320 KB Output is correct
76 Correct 3434 ms 93588 KB Output is correct
77 Correct 4299 ms 130216 KB Output is correct
78 Correct 4544 ms 130616 KB Output is correct
79 Correct 4276 ms 130348 KB Output is correct
80 Correct 4374 ms 130260 KB Output is correct
81 Correct 4243 ms 124736 KB Output is correct
82 Correct 3531 ms 97388 KB Output is correct
83 Correct 4396 ms 130320 KB Output is correct
84 Correct 4311 ms 130828 KB Output is correct
85 Correct 4333 ms 130508 KB Output is correct
86 Correct 4296 ms 130048 KB Output is correct
87 Correct 4094 ms 125420 KB Output is correct
88 Correct 3394 ms 97488 KB Output is correct
89 Correct 3007 ms 103972 KB Output is correct
90 Correct 3491 ms 111616 KB Output is correct
91 Correct 4043 ms 120756 KB Output is correct
92 Correct 4182 ms 123124 KB Output is correct
93 Correct 4496 ms 126104 KB Output is correct
94 Correct 4252 ms 127668 KB Output is correct
95 Correct 4251 ms 129480 KB Output is correct
96 Correct 4362 ms 129792 KB Output is correct
97 Correct 4268 ms 129928 KB Output is correct
98 Correct 4380 ms 129984 KB Output is correct
99 Correct 4265 ms 129456 KB Output is correct
100 Correct 4260 ms 129888 KB Output is correct