Submission #1048323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048323		KiaRez	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	238 ms	125916 KiB

Main

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 6e5+23, lg = 18;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int n, tim, rev[N], par[lg][N], p[N], q[N], tin[N], tout[N];
int h[N], lazy[2*N], mark[N];
pii seg[2*N];
vector<int> adj[N], tree[N];

int getPar(int v, int dist) {
    for(int i=0;i<lg;i++) if((dist>>i)%2==1) v=par[i][v];
    return v;
}

int LCA(int v, int u) {
    if(h[u] < h[v]) swap(v,u);
    u = getPar(u, h[u]-h[v]);
    if(v == u) return v;
    for(int i=lg-1; i>=0; i--) {
        if(par[i][v] != par[i][u]) {
            v=par[i][v], u=par[i][u];
        }
    }
    return par[0][v];
}

void init(int v, int p=0) {
    tin[v] = ++tim, h[v] = h[p] + 1, par[0][v] = p;
    rev[tim] = v;
    for(int i=1; i<lg; i++) par[i][v]=par[i-1][par[i-1][v]];
    for(auto u : adj[v]) {
        if(u == p) continue;
        init(u, v);
    }
    tout[v] = tim+1;
}

void build(int ind=1) {
    if(ind >= (1<<lg)) {
        seg[ind].S = p[rev[ind - (1<<lg) + 1]];
        return;
    }
    build(2*ind); build(2*ind+1);
    seg[ind] = max(seg[2*ind], seg[2*ind+1]);
}

void pushdown(int ind) {
    seg[ind].F += lazy[ind];
    (ind < (1<<lg)) && (lazy[2*ind] += lazy[ind]);
    (ind < (1<<lg)) && (lazy[2*ind+1] += lazy[ind]);
    lazy[ind] = 0;
}

void update(int l, int r, int x, int ind=1, int lc=1, int rc=(1<<lg)+1) {
    pushdown(ind);
    if(l >= rc || lc >= r) return;
    if(lc >= l && rc <= r) {
        lazy[ind] += x; pushdown(ind);
        return;
    }
    int mid = (lc+rc)/2;
    update(l, r, x, 2*ind, lc, mid);
    update(l, r, x, 2*ind+1, mid, rc);
    seg[ind] = max(seg[2*ind], seg[2*ind+1]);
}

pii query(int l, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) {
    pushdown(ind);
    if(l >= rc || lc >= r) return Mp(0, 0);
    if(lc >=l && rc <= r) return seg[ind];
    int mid = (lc+rc)/2;
    return max(query(l,r,2*ind,lc,mid), query(l,r,2*ind+1,mid,rc));
}

void divide(int v) {
    mark[v] = 1;
    int p = 0;
    for(auto u : adj[v]) {
        if(mark[u] == 1) continue;
        if(u == par[0][v]) {
            p = u;
            continue;
        }
        update(1, n+1, -1);
        update(tin[u], tout[u], 1);
        int rt = q[query(tin[u], tout[u]).S];
        divide(rt);
        tree[v].pb(rt);
        // cout<<v<<' '<<rt<<endl;
        update(1, n+1, 1);
        update(tin[u], tout[u], -1);
    }

    if(p == 0) return;
    update(tin[v], tout[v], -1);
    int rt = q[query(1, n+1).S];
        // cout<<v<<' '<<rt<<endl;
    tree[v].pb(rt);
    divide(rt);
}

int dp[N];
void dfs(int v) {
    for(int u : tree[v]) {
        dfs(u);
        int lca = LCA(v, u);
        dp[v] = max(dp[v], dp[u]+h[v]+h[u]-2*h[lca]);
    }
    // fuck(v); fuck(dp[v]);
}

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

	cin>>n;
    for(int i=1; i<=n; i++) cin>>p[i], q[p[i]]=i;
    for(int v,u,i=1; i<n; i++) {
        cin>>v>>u; adj[v].pb(u); adj[u].pb(v);
    }

    init(q[n], 0);
    build(1);

    divide(q[n]);

    dfs(q[n]);

    cout<<dp[q[n]]<<endl;

	return 0;
}

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