답안 #954614

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954614	2024-03-28T08:25:54 Z	sleepntsheep	Cat Exercise (JOI23_ho_t4)	C	31 / 100	152 ms	149016 KB

Main

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #954614

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 10.0 / 10.0

Subtask #5 0 / 20.0

Subtask #6 0 / 23.0

Subtask #7 0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
7.0 / 7.0

Subtask #4
10.0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
0 / 23.0

Subtask #7
0 / 26.0