Submission #1241580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241580		yoshi_33550336	Cat Exercise (JOI23_ho_t4)	C++20	41 / 100	2094 ms	56672 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> adj[200000];
int depth[200000];
int binlift[18][200000];
int in_queue[200000];
int d[200000];
deque<int> qu;
void dfs(int i, int par)
{
    binlift[0][i] = par;
    for (auto j : adj[i])
    {
        if (j != par)
        {
            depth[j] = depth[i] + 1;
            dfs(j, i);
        }
    }
}
int n;
int lca(int l, int r)
{
    assert(l >= 0);
    assert(r >= 0);
    assert(l < n);
    assert(r < n);
    if (depth[l] > depth[r])
        swap(l, r);
    int x = depth[r] - depth[l];
    for (int R = __lg(x); R >= 0; R--)
    {
        if ((x >> R) & 1)
        {
            r = binlift[R][r];
            x -= 1 << R;
        }
    }
    if (l == r)
        return l;
    else
    {
        for (int R = __lg(depth[l]); R >= 0; R--)
        {
            if (binlift[R][r] != binlift[R][l])
            {
                l = binlift[R][l];
                r = binlift[R][r];
            }
        }
        return binlift[0][l];
    }
}
int dist(int u, int v)
{
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
int par[200000];

int find_(int x)
{
    int counter = 0;
    while (par[x] != x)
        counter++, x = par[x], assert(counter < n);
    return x;
}
void Yoshi()
{

    cin >> n;
    vector<int> p(n), invp(n);
    for (auto &i : p)
        cin >> i, i--;
    for (int i = 0; i < n; i++)
        invp[p[i]] = i, par[i] = i;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(0, -1);
    for (int i = 1; i < 18; i++)
        for (int j = 0; j < n; j++)
        {
            if (binlift[i - 1][j] == -1)
                binlift[i][j] = -1;
            else
                binlift[i][j] = binlift[i - 1][binlift[i - 1][j]];
        }
    vector<int> DP(n);
    for (int i = 0; i < n; i++)
    {
        for (auto &k : adj[invp[i]])
            if (p[k] < i)
            {
                int u = find_(k);
                DP[invp[i]] = max(DP[invp[i]], DP[u] + dist(u, invp[i]));
            }
        for (auto &k : adj[invp[i]])
            if (p[k] < i)
                par[find_(k)] = invp[i];
    }
    cout << DP[invp[n - 1]] << endl;
}
signed main()
{
#ifndef yoshi_likes_e4
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(problem ".inp", "r"))
    {
        freopen(problem ".inp", "r", stdin);
        freopen(problem ".out", "w", stdout);
    }
#endif
    init();
    int t = 1;
#if multitest
    cin >> t;
#endif
    while (t--)
        Yoshi();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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