Submission #954614

#	Time	Username	Problem	Language	Result	Execution time	Memory
954614		sleepntsheep	Cat Exercise (JOI23_ho_t4)	C11	31 / 100	152 ms	149016 KiB

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 (stderr)

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 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26