Submission #805912

#	Time	Username	Problem	Language	Result	Execution time	Memory
805912		guagua0407	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	248 ms	60568 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=2e5+5;
vector<int> adj[mxn],adj2[mxn];
vector<int> nxt[mxn];
int p[mxn];
int depth[mxn];
int up[20][mxn];


struct DSU{
    vector<int> e;
    vector<int> mx;
    DSU(int n){
        e=vector<int>(n,-1);
        mx=vector<int>(n);
        for(int i=0;i<n;i++){
            mx[i]=i;
        }
    }

    int find(int x){
        return (e[x]<0?x:e[x]=find(e[x]));
    }
    bool unite(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b) return false;
        if(e[a]>e[b]) swap(a,b);
        mx[a]=max(mx[a],mx[b]);
        e[a]+=e[b];
        e[b]=a;
        return true;
    }
};

void dfs(int v,int p=-1){
    if(p!=-1) depth[v]=depth[p]+1;
    if(p!=-1) up[0][v]=p;
    for(auto u:adj2[v]){
        if(u==p) continue;
        dfs(u,v);
    }
}

int lca(int a,int b){
    if(depth[a]<depth[b]) swap(a,b);
    int len=depth[a]-depth[b];
    for(int i=0;i<20;i++){
        if(len&(1<<i)){
            a=up[i][a];
        }
    }
    if(a==b) return a;
    for(int i=19;i>=0;i--){
        int ta=up[i][a];
        int tb=up[i][b];
        if(ta!=tb){
            a=ta;
            b=tb;
        }
    }
    return up[0][a];
}

ll dist(int a,int b){
    int c=lca(a,b);
    return depth[a]+depth[b]-2*depth[c];
}

ll solve(int v){
    ll ans=0;
    for(auto u:nxt[v]){
        ans=max(ans,dist(u,v)+solve(u));
    }
    return ans;
}

int main() {_
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>p[i];
        p[i]--;
    }
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        a=p[a];
        b=p[b];
        adj2[a].push_back(b);
        adj2[b].push_back(a);
        if(a>b) swap(a,b);
        adj[b].push_back(a);
    }
    DSU dsu(n);
    for(int i=0;i<n;i++){
        for(auto v:adj[i]){
            nxt[i].push_back(dsu.mx[dsu.find(v)]);
        }
        for(auto v:adj[i]){
            dsu.unite(i,v);
        }
    }
    dfs(0);
    for(int i=1;i<20;i++){
        for(int j=0;j<n;j++){
            up[i][j]=up[i-1][up[i-1][j]];
        }
    }
    cout<<solve(n-1);
    return 0;
}
//maybe its multiset not set

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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