oj.uz

Submission #954614

# Submission time Handle Problem Language Result Execution time Memory
954614 2024-03-28T08:25:54 Z sleepntsheep Cat Exercise (JOI23_ho_t4) C
31 / 100
 152 ms 149016 KB 
#include<stdio.h>

#define N 200001

int n,p[N],tin[N],tout[N],aux[N],paux[N],dd[N],pp[N],jj[N];
struct { int to,prev; } e[N]; int ee,h[N];

int timer=1;
void dfs(int u,int p)
{
    aux[tin[u]=timer++]=u;
    for(int j=h[u];j;j=e[j].prev)if(e[j].to-p)
    {
        int v=e[j].to;
        pp[v]=u;
        jj[v]=(dd[u]-dd[jj[u]]==dd[jj[u]]-dd[jj[jj[u]]])?jj[jj[u]]:u;
        dd[v]=dd[u]+1;
        dfs(e[j].to,u);
    }
    tout[u]=timer-1;
}

long long min_(long long a,long long b){return a<b?a:b;}
long long max_(long long a,long long b){return a>b?a:b;}

long long t[N<<2],lz[N<<2];

void build(int v,int l,int r)
{
    if(l==r){t[v]=p[aux[l]];return;}
    build(v<<1,l,(l+r)/2);
    build(v<<1|1,(l+r)/2+1,r);
    t[v]=max_(t[v<<1],t[v<<1|1]);
}
void upd(int v,int l,int r,int x,int y,int k)
{
    if(r<x||y<l)return;
    if(x<=l&&r<=y) { lz[v]+=k; return; }
    upd(v<<1,l,(l+r)/2,x,y,k);
    upd(v<<1|1,(l+r)/2+1,r,x,y,k);
    t[v]=max_(t[v<<1]+lz[v<<1],t[v<<1|1]+lz[v<<1|1]);
}
long long get(){return t[1]+lz[1];}

int lca(int u,int v)
{
    if(dd[u]>dd[v])return lca(v,u);
    while(dd[v]>dd[u])
        v=dd[jj[v]]>=dd[u]?jj[v]:pp[v];
    while(u-v)
        if(jj[v]!=jj[u])u=jj[u],v=jj[v];
        else u=pp[u],v=pp[v];
    return u;
}

int dist(int u,int v){return dd[u]+dd[v]-2*dd[lca(u,v)];}

long long dfs1(int u)
{
    long long ans=0,next;

    upd(1,1,n,tin[u],tout[u],-1e9);
    next=get();
    if(next>=1)ans=max_(ans,dfs1(paux[next])+dist(paux[next],u));
    upd(1,1,n,1,tin[u]-1,-1e9);
    upd(1,1,n,tout[u]+1,n,-1e9);

    for(int j=h[u];j;j=e[j].prev)
    {
        int v=e[j].to;
        if(v!=pp[u])
        {
            upd(1,1,n,tin[v],tout[v],1e9);
            next=get();
            if(next>=1)ans=max_(ans,dfs1(paux[next])+dist(paux[next],u));
            upd(1,1,n,tin[v],tout[v],-1e9);
        }
    }

    upd(1,1,n,1,n,1e9);
    return ans;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",p+i),paux[p[i]]=i;
    for(int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),e[++ee].to=v,e[ee].prev=h[u],h[u]=ee,e[++ee].to=u,e[ee].prev=h[v],h[v]=ee;

    pp[1]=jj[1]=1;
    dfs(1,1);
    build(1,1,n);

    printf("%lld\n",dfs1(paux[n]));
    return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:86:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     scanf("%d",&n);
      |     ^~~~~~~~~~~~~~
Main.c:87:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     for(int i=1;i<=n;++i)scanf("%d",p+i),paux[p[i]]=i;
      |                          ^~~~~~~~~~~~~~~
Main.c:88:29: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     for(int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),e[++ee].to=v,e[ee].prev=h[u],h[u]=ee,e[++ee].to=u,e[ee].prev=h[v],h[v]=ee;
      |                             ^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8792 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8792 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 2 ms 8536 KB Output is correct
17 Correct 1 ms 8608 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8792 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 2 ms 8536 KB Output is correct
17 Correct 1 ms 8608 KB Output is correct
18 Correct 5 ms 9308 KB Output is correct
19 Correct 5 ms 9304 KB Output is correct
20 Correct 5 ms 9308 KB Output is correct
21 Correct 6 ms 9308 KB Output is correct
22 Correct 6 ms 9308 KB Output is correct
23 Correct 5 ms 9308 KB Output is correct
24 Correct 5 ms 9304 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8792 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 2 ms 8536 KB Output is correct
17 Correct 1 ms 8608 KB Output is correct
18 Correct 5 ms 9308 KB Output is correct
19 Correct 5 ms 9304 KB Output is correct
20 Correct 5 ms 9308 KB Output is correct
21 Correct 6 ms 9308 KB Output is correct
22 Correct 6 ms 9308 KB Output is correct
23 Correct 5 ms 9308 KB Output is correct
24 Correct 5 ms 9304 KB Output is correct
25 Correct 1 ms 8536 KB Output is correct
26 Correct 5 ms 9304 KB Output is correct
27 Correct 5 ms 9556 KB Output is correct
28 Correct 6 ms 9048 KB Output is correct
29 Correct 5 ms 9052 KB Output is correct
30 Correct 5 ms 8796 KB Output is correct
31 Correct 6 ms 8796 KB Output is correct
32 Correct 8 ms 8792 KB Output is correct
33 Correct 7 ms 9048 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8792 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 2 ms 8536 KB Output is correct
17 Correct 1 ms 8608 KB Output is correct
18 Correct 5 ms 9308 KB Output is correct
19 Correct 5 ms 9304 KB Output is correct
20 Correct 5 ms 9308 KB Output is correct
21 Correct 6 ms 9308 KB Output is correct
22 Correct 6 ms 9308 KB Output is correct
23 Correct 5 ms 9308 KB Output is correct
24 Correct 5 ms 9304 KB Output is correct
25 Runtime error 152 ms 149016 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Runtime error 142 ms 131308 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8792 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 2 ms 8536 KB Output is correct
17 Correct 1 ms 8608 KB Output is correct
18 Correct 5 ms 9308 KB Output is correct
19 Correct 5 ms 9304 KB Output is correct
20 Correct 5 ms 9308 KB Output is correct
21 Correct 6 ms 9308 KB Output is correct
22 Correct 6 ms 9308 KB Output is correct
23 Correct 5 ms 9308 KB Output is correct
24 Correct 5 ms 9304 KB Output is correct
25 Correct 1 ms 8536 KB Output is correct
26 Correct 5 ms 9304 KB Output is correct
27 Correct 5 ms 9556 KB Output is correct
28 Correct 6 ms 9048 KB Output is correct
29 Correct 5 ms 9052 KB Output is correct
30 Correct 5 ms 8796 KB Output is correct
31 Correct 6 ms 8796 KB Output is correct
32 Correct 8 ms 8792 KB Output is correct
33 Correct 7 ms 9048 KB Output is correct
34 Runtime error 152 ms 149016 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -