Submission #758416

#	Time	Username	Problem	Language	Result	Execution time	Memory
758416		Jarif_Rahman	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	383 ms	52248 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct segtree{
    int k;
    vector<int> v;
    segtree(int n){
        k = 1;
        while(k < n) k*=2;
        k*=2;
        v.resize(k, -1);
    }
    void upd(int in, int x){
        in+=k/2;
        v[in] = x;
        in/=2;
        while(in > 0){
            v[in] = max(v[2*in], v[2*in+1]);
            in/=2;
        }
    }
    int get(int l, int r, int nd, int a, int b){
        if(b < l || a > r) return -1;
        if(a >= l && b <= r) return v[nd];
        int c = (a+b)/2;
        return max(get(l, r, 2*nd, a, c), get(l, r, 2*nd+1, c+1, b));
    }
    int get(int l, int r){
        return get(l, r, 1, 0, k/2-1);
    }
};

const int K = 18;
int n;
vector<vector<int>> v;
vector<int> p, pp;
vector<int> anc[K];
vector<int> depth, sz;
vector<int> pos;

int intime = 0;
void pre_dfs(int nd, int ss, int d){
    pos[nd] = intime++;
    depth[nd] = d;
    if(ss != -1) anc[0][nd] = ss;
    for(int x: v[nd]) if(x != ss) pre_dfs(x, nd, d+1), sz[nd]+=sz[x];
}

int get_anc(int nd, int h){
    for(int i = 0; i < K; i++){
        if(h&1) nd = anc[i][nd];
        h>>=1;
    }
    return nd;
}
int lca(int a, int b){
    if(depth[a] > depth[b]) swap(a, b);
    b = get_anc(b, depth[b]-depth[a]);
    if(a == b) return a;

    for(int i = K-1; i >= 0; i--) if(anc[i][a] != anc[i][b])
        a = anc[i][a], b = anc[i][b];

    return anc[0][a];
}
int dis(int a, int b){
    return depth[a]+depth[b]-2*depth[lca(a, b)];
}

ll ans = 0;
segtree seg(0);

void dfs(int nd, int ss, ll cur){
    ans = max(ans, cur);
    seg.upd(pos[nd], -1);

    for(int x: v[nd]) if(x != anc[0][nd]){
        int nxt = seg.get(pos[x], pos[x]+sz[x]-1);
        if(nxt == -1) continue;
        nxt = pp[nxt];
        dfs(nxt, x, cur+dis(nd, nxt));
    }

    int nxt = seg.get(pos[ss], pos[ss]+sz[ss]-1);
    if(nxt == -1) return;
    nxt = pp[nxt];
    dfs(nxt, ss, cur+dis(nd, nxt));
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    v.resize(n);
    p.resize(n), pp.resize(n);
    fill(anc, anc+K, vector<int>(n, 0));
    depth.resize(n), sz.assign(n, 1);
    pos.resize(n);

    for(int &x: p) cin >> x, x--;
    for(int i = 0; i < n; i++) pp[p[i]] = i;

    for(int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b; a--, b--;
        v[a].pb(b);
        v[b].pb(a);
    }

    pre_dfs(0, -1, 0);
    for(int p = 1; p < K; p++) for(int i = 0; i < n; i++) anc[p][i] = anc[p-1][anc[p-1][i]];

    seg = segtree(n);
    for(int i = 0; i < n; i++) seg.upd(pos[i], p[i]);

    dfs(pp[n-1], 0, 0);
    cout << ans << "\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