Submission #888267

#	Time	Username	Problem	Language	Result	Execution time	Memory
888267		ace5	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	483 ms	69972 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int maxn = 200001;
const int maxlogn = 19;

vector<int> g[maxn];
int h[maxn];
int p[maxn];
pair<int,int> mp[maxn];
int dp[maxn];
int pp[maxn];
int la[maxlogn][maxn];
int d[maxn];
int tin[maxn],tout[maxn];

int times = 0;

int get(int v)
{
    if(p[v] == v)
        return v;
    else
        return p[v] = get(p[v]);
}
void unio(int u,int v)
{
    u = get(u);
    v = get(v);
    if(u == v)
        return ;
    mp[v] = max(mp[u],mp[v]);
    p[u] = v;
    return ;
}
void dfs(int v,int pf,int dd)
{
    tin[v] = times++;
    pp[v] = pf;
    d[v] = dd;
    for(auto u:g[v])
    {
        if(u != pf)
            dfs(u,v,dd+1);
    }
    tout[v] = times++;
    return ;
}
int lp(int a,int b)
{
    int a2 = a;
    for(int i = maxlogn-1;i >= 0;--i)
    {
        //if(i == 0)
       // {
       //     cout << la[i][a] << ' ';
      //  }
        if(tin[la[i][a]] > tin[b] || tout[la[i][a]] < tout[b])
        {
            a = la[i][a];
        }
    }
   // cout << a << ' ';
    if(tin[a] > tin[b] || tout[a] < tout[b])
    {
        a = pp[a];
    }
  //  cout << a2 << ' ' << b << ' ' << a << "\n";
    return d[a2] + d[b] - 2*d[a];
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0;i < n;++i)
    {
        cin >> h[i];
    }
    for(int i = 0;i < n-1;++i)
    {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0,0,0);
    for(int i = 0;i < maxlogn;++i)
    {
        for(int j = 0;j < n;++j)
        {
            if(i == 0)
                la[i][j] = pp[j];
            else
                la[i][j] = la[i-1][la[i-1][j]];
        }
    }
    vector<int> ind(n);
    vector<bool> en(n);
    for(int j = 0;j < n;++j)
    {
        p[j] = j;
        mp[j] = {h[j],j};
        ind[j] = j;
        en[j] = 0;
    }
    sort(ind.begin(),ind.end(),[&](int a,int b){return h[a] < h[b];});
    for(int j = 0;j < n;++j)
    {
        int v = ind[j];
        en[v] = 1;
        dp[v] = 0;
        for(auto u:g[v])
        {
            if(en[u])
            {
               int tv = mp[get(u)].second;
            //   cout << tv << ' ' << dp[tv] << ' ' << v << ' ' << lp(v,tv);
               dp[v] = max(dp[v],dp[tv] + lp(v,tv));
            }

        }
        for(auto u:g[v])
        {
            if(en[u])
            {
                unio(v,u);
            }
        }
      //  cout << dp[v] << "!\n";
        if(j == n-1)
            cout << dp[v] << "\n";

    }
}

• 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