Submission #919667

#	Time	Username	Problem	Language	Result	Execution time	Memory
919667		andrei_iorgulescu	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	381 ms	70996 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n,p[200005],pos[200005];
vector<int>g[200005];
int bl[20][200005];
int lg[200005];
int tt[200005],sz[200005];
int cine[200005];
int h[200005],t[200005];
int dp[200005];

void dfs(int nod,int tata)
{
    for (auto vecin : g[nod])
    {
        if (vecin != tata)
        {
            h[vecin] = 1 + h[nod];
            t[vecin] = nod;
            dfs(vecin,nod);
        }
    }
}

int root(int x)
{
    while (x != tt[x])
        x = tt[x];
    return x;
}

void unite(int x,int y)
{
    x = root(x);
    y = root(y);
    if (x == y)
        return;
    if (sz[x] < sz[y])
        swap(x,y);
    tt[y] = x;
    sz[x] += sz[y];
    if (p[cine[y]] > p[cine[x]])
        cine[x] = cine[y];
}

int lca(int x,int y)
{
    if (h[x] > h[y])
        swap(x,y);
    for (int st = lg[n]; st >= 0; st--)
        if (h[y] - (1 << st) >= h[x])
            y = bl[st][y];
    if (x == y)
        return x;
    for (int st = lg[n]; st >= 0; st--)
        if (bl[st][x] != bl[st][y])
            x = bl[st][x],y = bl[st][y];
    return t[x];
}

int dist(int x,int y)
{
    return h[x] + h[y] - 2 * h[lca(x,y)];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i],pos[p[i]] = i;
    for (int i = 1; i <= n; i++)
        tt[i] = i,sz[i] = 1,cine[i] = i;
    for (int i = 1; i < n; i++)
    {
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0);
    for (int i = 2; i <= n; i++)
        lg[i] = 1 + lg[i / 2];
    for (int i = 1; i <= n; i++)
        bl[0][i] = t[i];
    for (int j = 1; j <= lg[n]; j++)
        for (int i = 1; i <= n; i++)
            bl[j][i] = bl[j - 1][bl[j - 1][i]];
    for (int i = 1; i <= n; i++)
    {
        int nod = pos[i];
        for (auto vecin : g[nod])
        {
            if (p[vecin] < p[nod])
            {
                int x = cine[root(vecin)];
                dp[nod] = max(dp[nod],dp[x] + dist(nod,x));
                unite(nod,vecin);
            }
        }
    }
    cout << dp[pos[n]];
    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