Submission #1209125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209125		kitkat12	Cat Exercise (JOI23_ho_t4)	C++20	0 / 100	2 ms	5192 KiB

Main

// Problem URL: https://oj.uz/problem/view/JOI23_ho_t4
// Finish Time: 5/28/2025, 2:16:03 PM AC
// Start Time: 5/27/2025, 9:44:51 PM

// Categories: Data Structures, Lazy Segment tree, Dsu, Graphs, DFS, LCA, Trees
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int i = a; i < b; i++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define max(a,b) max<ll>(a,b)
#define min(a,b) min<ll>(a,b)

const int nmax = 2e5+3;
const int LOG = 32-__builtin_clz(nmax);

vector<int> adj[nmax];
int p[nmax], pos[nmax];
int n;
bool obst[nmax];

int t[2*nmax], d[nmax];
int h;
void apply(int x, int v){
    t[x]=v;
    if(x<n)d[x]=v;
}
void builds(){for(int i = n-1; i>0; i--)t[i]=max(t[i*2],t[i*2+1]);}
void build(int x){
    while(x>1)x>>=1, t[x]=(d[x]!=0?d[x]:max(t[x*2],t[x*2+1]));
}
void push(int x){
    for(int s = h; s>0; s--){
        int i = x>>s;
        if(d[i]!=0){
            apply(i<<1, d[i]);
            apply(i<<1|1, d[i]);
            d[i]=0;
        }
    }
}
void assign(int l, int r, int v){
    l+=n; r+=n;
    int l0=l, r0=r;
    for(;l<r;l>>=1,r>>=1){
        if(l&1)apply(l++,v);
        if(r&1)apply(--r,v);
    }
    build(l0);
    build(r0-1);
}
int get(int l, int r){
    l+=n;r+=n;
    push(l);
    push(r-1);
    int res = -1;
    for(;l<r;l>>=1,r>>=1){
        if(l&1)res=max(res,t[l++]);
        if(r&1)res=max(res,t[--r]);
    }
    return res;
}


int timer = -1;
int dep[nmax], dt[nmax], ft[nmax], jmp[nmax][LOG+1];
void dfs(int u, int par=-1){
    dt[u]=++timer;
    for(int v : adj[u]){
        if(v==par)continue;
        jmp[v][0]=u;
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
    ft[u]=timer;
}
void prec_lca(){
    for(int j = 1; j<=LOG; j++){
        for(int i = 1; i<=n; i++){
            jmp[i][j] = jmp[jmp[i][j-1]][j-1];
        }
    }
}
int lca(int a, int b){
    if(dep[a]<dep[b])swap(a,b);
    //podigni a na istu visinu kao b
    int dif = dep[a]-dep[b];
    for(int i = 0; i<=LOG; i++){
        if(dif&(1<<i)){
            a = jmp[a][i];
        }
    }
    if(a==b)return a;

    for(int i = LOG; i>=0; i--){
        if(jmp[a][i] != jmp[b][i]){
            a = jmp[a][i];
            b = jmp[b][i];
        }
    }
    return jmp[a][0];
}


int skip[nmax];
// ── query ──  O(α N)
int top(int v)               // highest free ancestor with blocked parent
{
    if (obst[ skip[v] ]) return v;          // good already
    return skip[v] = top(skip[v]);          // splice and recurse
}

// ── update ──  called exactly once for every vertex, when you block it
inline void block(int v)
{
    obst[v] = true;
    int u = jmp[v][0];
    while (u && obst[u]) u = skip[u];  
    skip[v] = u ? top(u) : 0;
}

ll maxmoves(int mn){
    ll res = 0;
    // obst[mn]=1;
    block(mn);
    assign(dt[mn],dt[mn]+1,-1);
    // prvo odradi sva podstabla
    for(int v : adj[mn]){
        if(v==jmp[mn][0]) continue;
        int maxv = get(dt[v],ft[v]+1);
        if(maxv==-1)continue;
        int maxnode = pos[maxv];
        res = max(res, maxmoves(maxnode) + (dep[maxnode] - dep[mn]));

        // ocrni celo podstablo 
        if(p[mn]==n) continue;
        assign(dt[maxnode], ft[maxnode]+1, -1);
    }

    // nadji poslednjeg ne blokiranog pretka  
    if(p[mn]!=n){
        // int maxv = top(mn);  
        int up = skip[mn];                 
        int maxv = obst[up] ? mn : top(up);
        if(maxv != mn){
            maxv = get(dt[maxv],ft[maxv]+1);
            if(maxv!=-1){
                int maxnode = pos[maxv];
                res = max(res,maxmoves(maxnode) + dep[maxnode] + dep[mn] - 2*dep[lca(maxnode,mn)]);
                // assign(dt[maxnode], ft[maxnode] + 1, -1);
            }
        }
    }
    return res;
}

int main() 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>n;
    h = 31 - __builtin_clz(n);
    li(i,1,n+1){
        cin>>p[i];
        pos[p[i]]=i;
    }
    li(i,0,n-1){
        int a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(pos[n]);
    for (int v = 1; v <= n; ++v) {
        skip[v] = jmp[v][0];     
    }
    obst[0] = true;         

    li(i,1,n+1) t[dt[i]+n]=p[i];
    builds();
    prec_lca();
    cout<<maxmoves(pos[n]);
    return 0;
}

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