Submission #917674

#	Time	Username	Problem	Language	Result	Execution time	Memory
917674		berr	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	840 ms	127712 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
const int mod = 1e9+7;

struct dsu{
    int n;
    vector<int> p, s;
    vector<set<int>> st;

    dsu(int _n, vector<int> g){
        n = _n;
        p.resize(n);
        s.resize(n, 1);
        st.resize(n);

        iota(p.begin(), p.end(), 0);
    }

    int find(int x){
        if(x==p[x]) return x;
        return p[x] = find(p[x]);
    }

    int op(int x){
        int t = find(x);
        while(*st[t].begin()<=x&&st[t].size()>1){
            st[t].erase(st[t].begin());
        }
        return *st[t].begin();
    }
    int merge(int u, int v){
        u = find(u);
        v = find(v);

        if(u==v) return 0;
        if(s[u]<s[v]) swap(u, v);
        s[u] += s[v];
        p[v] = u;

        if(st[u].size() < st[v].size()){
            swap(st[u], st[v]);
        }

        for(auto i: st[v]) st[u].insert(i);

        return 1;
    }
};

struct LCA {                                                
        int root, n, cnt;

        vector<vector<int>> adj;  
        vector<array<int, 21>> par;
        vector<int> ti, to, d;

        LCA(vector<vector<int>> aadj, int r){ 
            adj = aadj; n = adj.size();
            par.resize(n);
            d.assign(n, 0);
            root = r; cnt = 0;
            ti.resize(n); to.resize(n);

            d[root] = -1;
            dfs(root, root);

            for (int i = 1; i < 21; i++){
                for(int l = 0; l<n; l++){
                    par[l][i] = par[par[l][i-1]][i-1];
                }
            }
        }
        
        void dfs(int v, int p){
            par[v][0] = p;
            ti[v] = cnt++;
            d[v] = d[p]+1;
            for (auto i: adj[v]){
                if (i != p) dfs(i, v); 
            }
            to[v] = cnt++;
        }

        bool ia(int u, int v){
            return ti[u] <= ti[v] && to[u] >= to[v];
        }

        int operator()(int u, int v){

            if(ia(u, v)) return u;
            if(ia(v, u)) return v;

            for(int i = 20; i>=0; i--){
                if(!ia(par[u][i], v)) u=par[u][i];
            }

            return par[u][0];
        }
      
      int distance(int u, int v){
        return d[u]+d[v]-2*d[(*this)(u, v)];
      }
};  

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;

    vector<int> val(n), id(n);
    vector<vector<int>> g(n);   


    for(auto &i: val) cin >> i, i--;

    dsu d(n, val);

    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int x, int y){
        return val[x] < val[y];
    });

    for(int i=0; i<n-1; i++){
        int x, y; cin >> x >> y;
        x--; y--;

        d.st[val[x]].insert(val[y]);
        d.st[val[y]].insert(val[x]);

        g[x].push_back(y);  
        g[y].push_back(x);
    }

    LCA lca(g, 0);

    vector<vector<int>> g2(n);
    int root = -1;

    for(auto i: id){
        if(val[i]==n-1){
            root = i;
            break;
        }
        int pf = d.op(val[i]);  
        d.merge(pf, val[i]);      

        g2[id[pf]].push_back(i);
    }       
    
    int ans = 0;
    auto dfs = [&](int v, int z, auto&& dfs)->void{
        ans = max(ans, z);
        for(auto i: g2[v]){
            dfs(i, z+lca.distance(v, i), dfs);
        }
    };

    dfs(root, 0, dfs);
    cout << ans;

}   

• 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