Submission #1132433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132433		AndrijaM	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	359 ms	94820 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
///#define endl '\n'

const int maxn=2e5+10;
const int sz=100;
const int mod=1e9+7;
const int logn=30;

int n;
bool vis[maxn];
int val[maxn];
vector<int>g[maxn];
int up[maxn][logn];
int dep[maxn];
int in[maxn];
int out[maxn];
int invin[maxn];
int pval[maxn];
pair<int,int>st[4*maxn];
int C=0;

void build(int L,int R,int pos)
{
    if(L==R)
    {
        st[pos]={pval[R],R};
        return ;
    }
    int mid=(L+R)/2;
    build(L,mid,2*pos);
    build(mid+1,R,2*pos+1);
    st[pos]=max(st[2*pos],st[2*pos+1]);
}

pair<int,int> query(int L,int R,int i,int j,int pos)
{
    if(i<=L && R<=j)
    {
        return st[pos];
    }
    pair<int,int>pom={-1,-1};
    int mid=(L+R)/2;
    if(i<=mid)
    {
        pom=max(pom,query(L,mid,i,j,2*pos));
    }
    if(mid<j)
    {
        pom=max(pom,query(mid+1,R,i,j,2*pos+1));
    }
    return pom;
}

void u(int L,int R,int idx,int pos)
{
    if(L==R)
    {
        st[pos]={0,0};
        return ;
    }
    int mid=(L+R)/2;
    if(idx<=mid)
    {
        u(L,mid,idx,2*pos);
    }
    else
    {
        u(mid+1,R,idx,2*pos+1);
    }
    st[pos]=max(st[2*pos],st[2*pos+1]);
}

void dfs(int node,int par,int d)
{
    up[node][0]=par;
    dep[node]=d;
    in[node]=C;
    invin[in[node]]=node;
    pval[in[node]]=val[node];
    C++;
    for(auto ax:g[node])
    {
        if(ax==par)continue;
        dfs(ax,node,d+1);
    }
    out[node]=C-1;
}

int LCAdis(int a,int b)
{
    if(dep[b]<dep[a])
    {
        swap(a,b);
    }
    int ans=dep[b]-dep[a];
    for(int i=logn-1;i>=0;i--)
    {
        if(up[b][i]!=-1 && dep[up[b][i]]>=dep[a])
        {
            b=up[b][i];
        }
    }
    if(a==b)
    {
        return ans;
    }
    for(int i=logn-1;i>=0;i--)
    {
        if(up[b][i]!=up[a][i] && up[b][i]!=-1)
        {
            b=up[b][i];
            a=up[a][i];
            ans+=(1<<i)*2;
        }
    }
    return ans+2;
}

int solve(int node,int h)
{
    vis[node]=1;
    u(0,n-1,in[node],1);
    int ans=0;
    for(auto j:g[node])
    {
        if(vis[j] || j==up[node][0])continue;
        pair<int,int>pom=query(0,n-1,in[j],out[j],1);
        ans=max(ans,LCAdis(invin[pom.second],node)+solve(invin[pom.second],j));
    }
    int p=h;
    if(up[node][0]!=-1 && !vis[up[node][0]])
    {
        pair<int,int>pom=query(0,n-1,in[p],out[p],1);
        ans=max(ans,LCAdis(invin[pom.second],node)+solve(invin[pom.second],h));
    }
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ///freopen("dulciuri.in","r",stdin);
    ///freopen("dulciuri.out","w",stdout);
    cin>>n;
    int idx=-1;
    for(int i=0;i<n;i++)
    {
        cin>>val[i];
        if(val[i]==n)
        {
            idx=i;
        }
    }
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(idx,-1,0);
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<logn;j++)
        {
            up[i][j]=-1;
        }
    }
    for(int j=1;j<30;j++)
    {
        for(int i=0;i<n;i++)
        {
            if(up[i][j-1]!=-1)
            {
                up[i][j]=up[up[i][j-1]][j-1];
            }
        }
    }
    build(0,n-1,1);
    cout<<solve(idx,idx)<<endl;
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26