oj.uz

Submission #873203

# Submission time Handle Problem Language Result Execution time Memory
873203 2023-11-14T15:48:05 Z PagodePaiva Cat Exercise (JOI23_ho_t4) C++17
7 / 100
 2 ms 10844 KB 
#include<bits/stdc++.h>
#define N 200010
#define LOGN 21
#define int long long

using namespace std;

int n;
int v[N];
vector <int> g[N];
vector <pair <int, int>> pp;
int res[N];

struct DSU{
    int pai[N];

    void init(){
        for(int i = 1;i <= n;i++) pai[i] = i;
    }

    int find(int x){
        return pai[x] = (x == pai[x] ? x : find(pai[x]));
    }

    void join(int a, int b){
        b = find(b);
        pai[b] = a;
        return;
    }
} dsu;

struct Sparse{
    int pai[N][LOGN];
    int height[N];


    void dfs(int v, int p){
        pai[v][0] = p;
        for(auto x : g[v]){
            if(x == p) continue;
            height[x] = height[v] + 1;
            dfs(x,v);
        }
        return;
    }

    void init(){
        height[1] = 0;
        dfs(1, 1);

        for(int t = 1;t < LOGN;t++){
            for(int i = 1;i <= n;i++){
                pai[t][i] = pai[pai[t][i-1]][i-1];
            }
        }
    }

    int query(int x, int y){
        if(height[x] > height[y]) swap(x, y);
        
        int t = height[y] - height[x];

        for(int i = 0;i < LOGN;i++){
            if((t & (1 << i)) != 0){
                y = pai[y][i];
            }
        }

        if(x == y) return x;

        for(int i = LOGN-1;i >= 0;i--){
            if(pai[x][i] != pai[y][i]){
                x = pai[x][i];
                y = pai[y][i];
            }
        }

        return pai[x][0];
    }

    int dist(int x, int y, int lca){
        return height[x] + height[y] - 2*height[lca];
    }
} sparse;

int dist(int x, int y){
    int lca = sparse.query(x, y);

    return sparse.dist(x, y, lca);
}
int32_t main(){
    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;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(int i = 1;i <= n;i++){
        pp.push_back({v[i], i});
    }

    dsu.init();
    sparse.init();

    sort(pp.begin(), pp.end());

    for(auto aa : pp){
        int ver = aa.second;
        // cout << ver << '\n';

        for(auto x : g[ver]){
            if(v[x] > v[ver]) continue;
            x = dsu.find(x);
            // cout << x << ' ';
            res[ver] = max(res[ver], res[x] + dist(x, ver));
            dsu.join(ver, x);
        }

        // cout << '\n';
        // cout << '\n';   
    }

    int resp = 0;

    for(int i = 1;i <= n;i++) {resp = max(resp, res[i]);}

    cout << resp << '\n';
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10692 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10692 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Incorrect 2 ms 10588 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10692 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10692 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Incorrect 2 ms 10588 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10692 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10692 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Incorrect 2 ms 10588 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10692 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10692 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Incorrect 2 ms 10588 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Incorrect 2 ms 10672 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10692 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10692 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Incorrect 2 ms 10588 KB Output isn't correct
12 Halted 0 ms 0 KB -