Submission #1040233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040233		TAhmed33	Cat Exercise (JOI23_ho_t4)	C++98	41 / 100	113 ms	70108 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("trapv")
const int MAXN = 2e5 + 25;
const int B = 20;
typedef long long ll;
int a[MAXN], n;
vector <int> adj[MAXN];
int inv[MAXN];
ll dp[B][MAXN], dep[MAXN];
ll ans[MAXN];
struct DSU {
    int par[MAXN];
    void init () {
        for (int i = 1; i <= n; i++) {
            par[i] = i; 
        }
    }
    int find (int x) {
        return par[x] == x ? x : par[x] = find(par[x]);
    }
    void merge (int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (a[x] > a[y]) {
            par[y] = x;
        } else {
            par[x] = y;
        }
    }
} cur;
int jump (int x, int y) {
    for (int i = B - 1; i >= 0; i--) {
        if (y & (1 << i)) {
            x = dp[i][x];
        }
    }
    return x;
}
int lca (int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    y = jump(y, dep[y] - dep[x]);
    if (x == y) return x ;
    for (int i = B - 1; i >= 0; i--) {
        if (dp[i][x] != dp[i][y]) {
            x = dp[i][x], y = dp[i][x];
        }   
    }
    return dp[0][x];
}
ll dist (int x, int y) {
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
void dfs2 (int pos, int par) {
    for (auto j : adj[pos]) {
        if (j != par) {
            dp[0][j] = pos;
            for (int i = 1; i < B; i++) {
                dp[i][j] = dp[i - 1][dp[i - 1][j]];
            }
            dep[j] = 1 + dep[pos];
            dfs2(j, pos);
        }
    }
}
void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; inv[a[i]] = i;
    }
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs2(1, 0);
    cur.init();
    for (int x = 1; x <= n; x++) {
        int i = inv[x];
        for (auto j : adj[i]) {
            if (a[j] > a[i]) {
                continue;
            }
            ans[i] = max(ans[i], ans[cur.find(j)] + dist(cur.find(j), i));
            cur.merge(i, cur.find(j));
        }
    }
    cout << ans[inv[n]] << '\n';
}       
signed main () {
    ios::sync_with_stdio(0); cin.tie(0);
    int tc = 1; //cin >> tc;
    while (tc--) solve();
}

• 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