Submission #916521

#	Time	Username	Problem	Language	Result	Execution time	Memory
916521		Darren0724	Cat Exercise (JOI23_ho_t4)	C++17	41 / 100	205 ms	192424 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define all(x) x.begin(),x.end()
#define abcorz ios_base::sync_with_stdio(false);cin.tie(0);
const int N=400005;
const int K=20;
int n;
vector<int> v(N),deep(N);
struct sparse_table{
    vector<vector<int>> mx;
    int cmp(int i,int j){
        return (v[i]>v[j]?i:j);
    }
    void init(vector<int> &track){
        mx.resize(K,vector<int>(N));
        int n=track.size();
        for(int i=0;i<n;i++){
            mx[0][i]=track[i];
        }
        for(int i=1;i<K;i++){
            for(int j=0;j+(1<<i)<=n;j++){
                mx[i][j]=cmp(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
            }
        }
    }
    int ask(int l,int r){
        int p=__lg(r-l);
        return cmp(mx[p][l],mx[p][r-(1<<p)]);
    }
}sp;
struct sparse_table1{
    vector<vector<int>> mx;
    int cmp(int i,int j){
        return (deep[i]<deep[j]?i:j);
    }
    void init(vector<int> &track){
        mx.resize(K,vector<int>(N));
        int n=track.size();
        for(int i=0;i<n;i++){
            mx[0][i]=track[i];
        }
        for(int i=1;i<K;i++){
            for(int j=0;j+(1<<i)<=n;j++){
                mx[i][j]=cmp(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
            }
        }
    }
    int ask(int l,int r){
        int p=__lg(r-l);
        return cmp(mx[p][l],mx[p][r-(1<<p)]);
    }
}sp1;
vector<int> adj[N];
vector<int> track,in(N);
vector<int> tr[N];

void dfs(int k,int pa){
    in[k]=track.size();
    tr[k].push_back(track.size());
    track.push_back(k);
    for(int j:adj[k]){
        if(j==pa)continue;
        deep[j]=deep[k]+1;
        dfs(j,k);
        tr[k].push_back(track.size());
        track.push_back(k);
    }
}
int dis(int a,int b){
    if(in[a]>in[b])swap(a,b);
    int lca=sp1.ask(in[a],in[b]+1);
    return deep[a]+deep[b]-2*deep[lca];
}



int dc(int l,int r,int rec){
    if(r<=l){
        return 0;
    }
    int p=sp.ask(l,r);
    if(rec==-1)rec=p;
    int mx=0;
    int last=l-1;
    for(int j:tr[p]){
        if(j<l||j>r){
            continue;
        }
        mx=max(mx,dc(last+1,j,p));
        last=j;
    }
    mx=max(mx,dc(last+1,r,p));
    return dis(rec,p)+mx;
}


int32_t main(){
    abcorz;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,1);
    sp.init(track);
    sp1.init(track);
    cout<<dc(0,track.size(),-1)<<endl;
    return 0;
}

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