Submission #1040225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040225		TAhmed33	Cat Exercise (JOI23_ho_t4)	C++98	21 / 100	2040 ms	48328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
const int B = 19;
typedef long long ll;
int a[MAXN], n;
vector <int> adj[MAXN];
struct DSU {
    int par[MAXN];
    pair <int, int> mx[MAXN];
    void init () {
        for (int i = 1; i <= n; i++) {
            par[i] = i; mx[i] = {a[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;
        par[x] = y; if (mx[x].first > mx[y].first) {
            mx[y] = mx[x];
        }
    }
} cur;
vector <int> adj2[MAXN];
int dp[B][MAXN], dep[MAXN];
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];
}
int dist (int x, int y) {
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
ll dfs (int pos) {
    if (adj2[pos].empty()) return 0;
    ll mx = 0;
    for (auto j : adj2[pos]) {
        mx = max(mx, dist(j, pos) + dfs(j));
    }
    return mx;
}
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);
        }
    }
}
vector <int> yy;
void dfs3 (int pos, int par, int mx) {
    mx = max(mx, a[pos]);
    if (mx == a[pos] && par != -1) {
        yy.push_back(pos);
    }
    for (auto j : adj[pos]) {
        if (j != par) {
            dfs3(j, pos, mx);
        }
    }
}
void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[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);
    vector <int> ii;
    for (int i = 1; i <= n; i++) {
        ii.push_back(i);
    }
    sort(ii.begin(), ii.end(), [&] (int x, int y) {
        return a[x] < a[y];
    });
    cur.init();
/*    for (auto i : ii) {
        for (auto j : adj[i]) {
            if (a[j] > a[i]) {
                continue;
            }
            auto g = cur.mx[cur.find(j)].second;
            adj2[i].push_back(g);
            cur.merge(g, i);
        }
    }*/
    int root = -1;
    for (int i = 1; i <= n; i++) {
        if (a[i] == n) {
            root = i;
        }
    }
    for (int i = 1; i <= n; i++) {
        yy.clear();
        dfs3(i, -1, 0);
        sort(yy.begin(), yy.end(), [&] (int x, int y) {
            return a[x] < a[y];
        });
        if (!yy.empty()) {
            adj2[yy.front()].push_back(i);
        }
    }
    cout << dfs(root) << '\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: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26