oj.uz

Submission #924274

# Submission time Handle Problem Language Result Execution time Memory
924274 2024-02-08T18:50:12 Z vjudge1 Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 256 ms 47356 KB 
#include <bits/stdc++.h>

using namespace std;

struct DSU
{
    vector<int> v;
    vector<pair<int, int>> mx;
    void init(int n, vector<int>& a){
        v.assign(n, -1);
        mx.resize(n);
        for(int i = 0; i < n; i++){
            mx[i] = {a[i], i};
        }
    }
    int get(int x){return v[x] < 0 ? x : v[x] = get(v[x]);}
    void unite(int x, int y){
        x = get(x); y = get(y);
        if(x == y) return;
        if(v[x] > v[y]) swap(x, y);
        v[x] += v[y]; v[y] = x;
        mx[x] = max(mx[x], mx[y]);
    }
    int getMx(int x){
        x = get(x);
        return mx[x].second;
    }
};

const int LOG = 20;

vector<int> depth, parents;
vector<vector<int>> dp, adj;

void DFS(int x){
    for(int node : adj[x]){
        if(node != parents[x]){
            parents[node] = x;
            depth[node] = depth[x] + 1;
            DFS(node);
        }
    }
}

int kth(int x, int dist){
    for(int k = 0; k < LOG; k++){
        if((1 << k) & dist){
            x = dp[k][x];
        }
    }
    return x;
}

int lca(int a, int b){
    if(depth[a] > depth[b]) swap(a, b);
    b = kth(b, depth[b] - depth[a]);
    if(a==b) return a;
    int anc = a;
    for(int k = LOG - 1; k >= 0; k--){
        if(dp[k][a] == dp[k][b]) anc = dp[k][a];
        else{
            a = dp[k][a];
            b = dp[k][b];
        }
    }
    return anc;
}

int getDist(int a, int b){
    int anc = lca(a, b);
    return depth[a] + depth[b] - 2 * depth[anc];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    vector<pair<int, int>> P(N);
    vector<int> a(N);
    for(int i = 0; i < N; i++){
        int x; cin >> x;
        P[i] = {x, i};
        a[i] = x;
    }
    DSU UF; UF.init(N, a);
    adj.resize(N);
    for(int i = 0; i < N - 1; i++){
        int u, v; cin >> u >> v; u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    parents.assign(N, -1);
    depth.assign(N, 0);
    DFS(0);
    dp.assign(LOG, vector<int>(N));
    for(int k = 0; k < LOG; k++){
        for(int i = 0; i < N; i++){
            if(k == 0) dp[k][i] = parents[i];
            else{
                if(dp[k-1][i] == -1) dp[k][i] = -1;
                else dp[k][i] = dp[k-1][dp[k-1][i]];
            }
        }
    }
    sort(P.begin(), P.end());
    vector<int> ans(N, 0);
    for(pair<int, int> p : P){
        int i = p.second;
        for(int node : adj[i]){
            if(a[node] > a[i]) continue;
            ans[i] = max(ans[i], ans[UF.getMx(node)]+getDist(i, UF.getMx(node)));
            UF.unite(i, node);
        }
    }
    cout << ans[P[N-1].second] << "\n";
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 0 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 0 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 0 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 0 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 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 0 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 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 2 ms 1372 KB Output is correct
20 Correct 2 ms 1372 KB Output is correct
21 Correct 3 ms 1372 KB Output is correct
22 Correct 3 ms 1488 KB Output is correct
23 Correct 3 ms 1496 KB Output is correct
24 Correct 3 ms 1372 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 0 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 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 2 ms 1372 KB Output is correct
20 Correct 2 ms 1372 KB Output is correct
21 Correct 3 ms 1372 KB Output is correct
22 Correct 3 ms 1488 KB Output is correct
23 Correct 3 ms 1496 KB Output is correct
24 Correct 3 ms 1372 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 3 ms 1368 KB Output is correct
27 Correct 3 ms 1372 KB Output is correct
28 Correct 3 ms 1232 KB Output is correct
29 Correct 4 ms 1380 KB Output is correct
30 Correct 3 ms 1372 KB Output is correct
31 Correct 3 ms 1372 KB Output is correct
32 Correct 3 ms 1356 KB Output is correct
33 Correct 3 ms 1372 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 0 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 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 2 ms 1372 KB Output is correct
20 Correct 2 ms 1372 KB Output is correct
21 Correct 3 ms 1372 KB Output is correct
22 Correct 3 ms 1488 KB Output is correct
23 Correct 3 ms 1496 KB Output is correct
24 Correct 3 ms 1372 KB Output is correct
25 Incorrect 101 ms 47356 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 245 ms 37680 KB Output is correct
4 Correct 256 ms 37840 KB Output is correct
5 Correct 207 ms 37712 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 0 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 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 2 ms 1372 KB Output is correct
20 Correct 2 ms 1372 KB Output is correct
21 Correct 3 ms 1372 KB Output is correct
22 Correct 3 ms 1488 KB Output is correct
23 Correct 3 ms 1496 KB Output is correct
24 Correct 3 ms 1372 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 3 ms 1368 KB Output is correct
27 Correct 3 ms 1372 KB Output is correct
28 Correct 3 ms 1232 KB Output is correct
29 Correct 4 ms 1380 KB Output is correct
30 Correct 3 ms 1372 KB Output is correct
31 Correct 3 ms 1372 KB Output is correct
32 Correct 3 ms 1356 KB Output is correct
33 Correct 3 ms 1372 KB Output is correct
34 Incorrect 101 ms 47356 KB Output isn't correct
35 Halted 0 ms 0 KB -