Submission #945440

#	Time	Username	Problem	Language	Result	Execution time	Memory
945440		vladilius	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	433 ms	88956 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

struct dsu{
    vector<int> sz, p, m, a;
    int n;
    dsu(int ns, vector<int>& as){
        a = as;
        n = ns;
        p.resize(n + 1);
        sz.resize(n + 1);
        m.resize(n + 1);
        for (int i = 1; i <= n; i++){
            p[i] = m[i] = i;
            sz[i] = 1;
        }
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y){
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]){
            swap(x, y);
        }
        p[x] = y;
        sz[y] += sz[x];
        if (a[m[x]] > a[m[y]]){
            m[y] = m[x];
        }
    }
};

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> a(n + 1), p(n + 1);
    int s = 0;
    for (int i = 1; i <= n; i++){
        cin>>a[i];
        if (a[i] == n){
            s = i;
        }
        p[a[i]] = i;
    }
    vector<int> g[n + 1];
    for (int i = 1; i < n; i++){
        int u, v; cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dsu T(n + 1, a);
    
    vector<int> tin(n + 1), tout(n + 1), pw[n + 1], d(n + 1);
    int lg = ceil(log2(n)), timer = 0;
    for (int i = 1; i <= n; i++){
        pw[i].resize(lg);
    }
    function<void(int, int)> fill = [&](int v, int pr){
        tin[v] = timer++;
        pw[v][0] = pr;
        for (int i = 1; i < lg; i++){
            pw[v][i] = pw[pw[v][i - 1]][i - 1];
        }
        for (int i: g[v]){
            if (i == pr) continue;
            d[i] = d[v] + 1;
            fill(i, v);
        }
        tout[v] = timer++;
    };
    fill(1, 1);
    auto check = [&](int x, int y){
        return (tin[x] <= tin[y] && tout[x] >= tout[y]);
    };
    auto lca = [&](int x, int y){
        if (check(x, y)) return x;
        if (check(y, x)) return y;
        for (int i = lg - 1; i >= 0; i--){
            if (!check(pw[x][i], y)){
                x = pw[x][i];
            }
        }
        return pw[x][0];
    };
    auto dist = [&](int x, int y){
        return d[x] + d[y] - 2 * d[lca(x, y)];
    };
    vector<int> f(n + 1);
    for (int k = 1; k < n; k++){
        int i = p[k];
        for (int j: g[i]){
            if (a[j] > a[i]) continue;
            int v = T.m[T.get(j)];
            f[i] = max(f[i], f[v] + dist(i, v));
            T.unite(i, j);
        }
    }
    int out = 0;
    for (int i = 1; i <= n; i++){
        out = max(out, f[i] + dist(i, s));
    }
    cout<<out<<"\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