oj.uz

Submission #917674

# Submission time Handle Problem Language Result Execution time Memory
917674 2024-01-28T14:45:10 Z berr Cat Exercise (JOI23_ho_t4) C++17
100 / 100
 840 ms 127712 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 5 ms 3672 KB Output is correct
19 Correct 5 ms 3432 KB Output is correct
20 Correct 5 ms 3540 KB Output is correct
21 Correct 5 ms 3280 KB Output is correct
22 Correct 6 ms 3160 KB Output is correct
23 Correct 7 ms 3316 KB Output is correct
24 Correct 5 ms 3164 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 5 ms 3672 KB Output is correct
19 Correct 5 ms 3432 KB Output is correct
20 Correct 5 ms 3540 KB Output is correct
21 Correct 5 ms 3280 KB Output is correct
22 Correct 6 ms 3160 KB Output is correct
23 Correct 7 ms 3316 KB Output is correct
24 Correct 5 ms 3164 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 6 ms 3620 KB Output is correct
27 Correct 6 ms 3416 KB Output is correct
28 Correct 6 ms 3420 KB Output is correct
29 Correct 6 ms 3420 KB Output is correct
30 Correct 6 ms 3160 KB Output is correct
31 Correct 6 ms 3160 KB Output is correct
32 Correct 8 ms 3164 KB Output is correct
33 Correct 6 ms 3160 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 5 ms 3672 KB Output is correct
19 Correct 5 ms 3432 KB Output is correct
20 Correct 5 ms 3540 KB Output is correct
21 Correct 5 ms 3280 KB Output is correct
22 Correct 6 ms 3160 KB Output is correct
23 Correct 7 ms 3316 KB Output is correct
24 Correct 5 ms 3164 KB Output is correct
25 Correct 217 ms 127712 KB Output is correct
26 Correct 244 ms 126060 KB Output is correct
27 Correct 246 ms 126112 KB Output is correct
28 Correct 587 ms 116920 KB Output is correct
29 Correct 580 ms 117080 KB Output is correct
30 Correct 581 ms 116916 KB Output is correct
31 Correct 611 ms 117224 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 654 ms 111892 KB Output is correct
4 Correct 645 ms 111920 KB Output is correct
5 Correct 656 ms 111520 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 5 ms 3672 KB Output is correct
19 Correct 5 ms 3432 KB Output is correct
20 Correct 5 ms 3540 KB Output is correct
21 Correct 5 ms 3280 KB Output is correct
22 Correct 6 ms 3160 KB Output is correct
23 Correct 7 ms 3316 KB Output is correct
24 Correct 5 ms 3164 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 6 ms 3620 KB Output is correct
27 Correct 6 ms 3416 KB Output is correct
28 Correct 6 ms 3420 KB Output is correct
29 Correct 6 ms 3420 KB Output is correct
30 Correct 6 ms 3160 KB Output is correct
31 Correct 6 ms 3160 KB Output is correct
32 Correct 8 ms 3164 KB Output is correct
33 Correct 6 ms 3160 KB Output is correct
34 Correct 217 ms 127712 KB Output is correct
35 Correct 244 ms 126060 KB Output is correct
36 Correct 246 ms 126112 KB Output is correct
37 Correct 587 ms 116920 KB Output is correct
38 Correct 580 ms 117080 KB Output is correct
39 Correct 581 ms 116916 KB Output is correct
40 Correct 611 ms 117224 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 654 ms 111892 KB Output is correct
44 Correct 645 ms 111920 KB Output is correct
45 Correct 656 ms 111520 KB Output is correct
46 Correct 546 ms 122748 KB Output is correct
47 Correct 531 ms 123004 KB Output is correct
48 Correct 501 ms 122924 KB Output is correct
49 Correct 549 ms 122980 KB Output is correct
50 Correct 824 ms 111272 KB Output is correct
51 Correct 819 ms 111000 KB Output is correct
52 Correct 807 ms 110852 KB Output is correct
53 Correct 840 ms 111272 KB Output is correct