Submission #924572

#	Time	Username	Problem	Language	Result	Execution time	Memory
924572		adhityamv	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	408 ms	68544 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
int INF=1000000000;
const int N=200000;
const int K=400000;
int a[N];
vector<int> edges[N];
int parent[N];
int ind[N];
int m;
vector<int> et;
int focc[N];
int locc[N];
int depth[N];
void euler_tour(int u,int p){
    et.push_back(u);
    parent[u]=p;
    for(int  v:edges[u]){
        if(v==p) continue;
        depth[v]=depth[u]+1;
        euler_tour(v,u);
        et.push_back(u);
    }
}
const int ln=20;
int sparsetable[N][ln];
ll dist(int u,int v){
    if(u==v) return 0;
    if(depth[u]<depth[v]) swap(u,v);
    ll ans=0;
    for(int j=ln-1;j>=0;j--){
        if(depth[u]>=(1<<j)+depth[v]){
            u=sparsetable[u][j];
            ans+=(1<<j);
        }
    }
    if(u==v) return ans;
    for(int j=ln-1;j>=0;j--){
        if(sparsetable[u][j]!=sparsetable[v][j]){
            u=sparsetable[u][j];
            v=sparsetable[v][j];
            ans+=2*(1<<j);
        }
    }
    ans+=2;
    return ans;
}
int seg[4*K]={};
int lazy[4*K]={};
void Build(int l,int r,int pos){
    if(l==r){
        seg[pos]=a[et[l]];
        lazy[pos]=INF;
        return;
    }
    int m=(l+r)/2;
    Build(l,m,2*pos);
    Build(m+1,r,2*pos+1);
    seg[pos]=max(seg[2*pos],seg[2*pos+1]);
    lazy[pos]=INF;
}
void UpdateLazy(int l,int r,int pos){
    if(lazy[pos]==INF) return;
    seg[pos]=lazy[pos];
    if(l!=r){
        lazy[2*pos]=lazy[pos];
        lazy[2*pos+1]=lazy[pos];
    }
    lazy[pos]=INF;
}
void Update(int l,int r,int pos,int ql,int qr,int qval){
    if(ql>qr) return;
    UpdateLazy(l,r,pos);
    if(ql>r || qr<l) return;
    if(ql<=l && qr>=r){
        lazy[pos]=qval;
        UpdateLazy(l,r,pos);
        return;
    }
    int m=(l+r)/2;
    Update(l,m,2*pos,ql,qr,qval);
    Update(m+1,r,2*pos+1,ql,qr,qval);
    seg[pos]=max(seg[2*pos],seg[2*pos+1]);
}
int Query(int l,int r,int pos, int ql,int qr){
    if(ql>qr) return -INF;
    UpdateLazy(l,r,pos);
    if(ql>r || qr<l) return -INF;
    if(ql<=l && qr>=r){
        return seg[pos]; 
    }
    int m=(l+r)/2;
    return max(Query(l,m,2*pos,ql,qr),Query(m+1,r,2*pos+1,ql,qr));
}
bool blocked[N]={};
ll dfs(int u,int p){
    int cu=ind[Query(0,m-1,1,focc[u],locc[u])];
    blocked[cu]=true;
    ll ans=0;
    for(int v:edges[cu]){
        if(blocked[v]) continue;
        if(v==parent[cu]) continue;
        ll cans=dfs(v,cu);
        ans=max(ans,cans);
    }
    Update(0,m-1,1,focc[cu],locc[cu],-1);
    int val=Query(0,m-1,1,focc[u],locc[u]);
    if(val!=-1){
        ans=max(ans,dfs(u,cu));
    }
    if(p!=-1) ans+=dist(cu,p);
    return ans;
}
void solve(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
        a[i]--;
        ind[a[i]]=i;
    }
    for(int i=0;i<n-1;i++){
        int u,v;
        cin >> u >> v;
        u--,v--;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    depth[0]=0;
    euler_tour(0,-1);
    m=et.size();
    assert(m==2*n-1);
    for(int i=0;i<m;i++){
        locc[et[i]]=i;
    }
    for(int i=m-1;i>=0;i--){
        focc[et[i]]=i;
    }
    for(int i=0;i<n;i++) sparsetable[i][0]=parent[i];
    for(int j=0;j<ln-1;j++){
        for(int i=0;i<n;i++){
            if(sparsetable[i][j]==-1) sparsetable[i][j+1]=-1;
            else sparsetable[i][j+1]=sparsetable[sparsetable[i][j]][j];
        }
    }
    Build(0,m-1,1);
    cout << dfs(0,-1);
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t=1;
    //cin >> t;
    while(t--) solve();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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