oj.uz

Submission #884544

# Submission time Handle Problem Language Result Execution time Memory
884544 2023-12-07T16:15:51 Z wksp Cat Exercise (JOI23_ho_t4) C++14
54 / 100
 133 ms 62916 KB 
#include<bits/stdc++.h>

using namespace std;
const int n_max = 2 * 1e5 + 7;
const int max_log = 20;
int jump[max_log][n_max];

vector<int> graph[n_max];
int graph_up[n_max];
vector<int> graph_down[n_max];
int deep[n_max];
int open[n_max];
int leader[n_max];
int ans[n_max];
void init(int n){
    for(int i = 0; i    <= n; i++){
        leader[i] = i;
    }
}
void init_DFS(int v, int p = 0, int vallue = 1){
    graph_up[v] = p;
    deep[v] = vallue;
    for(auto u: graph[v]){
        if(u != p){
            init_DFS(u, v, vallue + 1);
            graph_down[v].push_back(u);
        }
    }
}
void init_jumps(int n){
    for(int i = 1; i <= n; i++){
        jump[0][i] = graph_up[i];
    }
    for(int i = 1; i < max_log; i++){
        for(int j = 1; j <= n; j++){
            jump[i][j] = jump[i-1][jump[i-1][j]];
        }
    }
}

int find(int v){
    if(v != leader[v]){
        leader[v] = find(leader[v]);
    }
    return leader[v];
}
int unite_without_lca(int v, int u){
    u = find(u);
    leader[u] = v;
    return (deep[u] - deep[v]) + ans[u];
}
int get_lca(int v, int u){
    if(deep[v] > deep[u]){
        int tmp = v;
        v = u;
        u = tmp;
    }
    int number = (1<<19);
    for(int i = 19; i > -1; i--){
        if(deep[u] - deep[v] >= number){
            u = jump[i][u];
        }
        number /= 2;
    }
    if(u == v){
        return v;
    }
    for(int i = 19; i > -1; i--){
        if(jump[i][u] != jump[i][v]){
            u = jump[i][u];
            v = jump[i][v];
        }
    }
    return jump[0][v];
}
int unite_with_lca(int v, int u){
    u = find(u);
    int lca = get_lca(v, u);
    leader[u] = v;
    return (deep[u] + deep[v] - 2 * deep[lca] + ans[u]);
}

void add_point(int v){
    ans[v] = 0;
    open[v] = 1;
    if(open[graph_up[v]] == 1){
        ans[v] = unite_with_lca(v, graph_up[v]); 
    }
    for(auto u: graph_down[v]){
        if(open[u] == 1){
            ans[v] = max(ans[v], unite_without_lca(v, u));
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    vector<pair<int, int>> tower_hight;
    int n;
    cin >> n;
    init(n);
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p;
        tower_hight.push_back({p, i});
    }
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    init_DFS(1);
    init_jumps(n);
    sort(tower_hight.begin(), tower_hight.end());
    for(auto [p, id]: tower_hight){
        add_point(id);
    }
    cout << ans[tower_hight[tower_hight.size()- 1].second] << '\n';

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:117:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |     for(auto [p, id]: tower_hight){
      |              ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 5 ms 29164 KB Output is correct
5 Correct 4 ms 29184 KB Output is correct
6 Correct 4 ms 29160 KB Output is correct
7 Correct 5 ms 29020 KB Output is correct
8 Correct 5 ms 29192 KB Output is correct
9 Correct 4 ms 29168 KB Output is correct
10 Correct 5 ms 29016 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 5 ms 29164 KB Output is correct
5 Correct 4 ms 29184 KB Output is correct
6 Correct 4 ms 29160 KB Output is correct
7 Correct 5 ms 29020 KB Output is correct
8 Correct 5 ms 29192 KB Output is correct
9 Correct 4 ms 29168 KB Output is correct
10 Correct 5 ms 29016 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 5 ms 29168 KB Output is correct
13 Correct 4 ms 29020 KB Output is correct
14 Correct 4 ms 29220 KB Output is correct
15 Correct 4 ms 29020 KB Output is correct
16 Correct 5 ms 29164 KB Output is correct
17 Correct 5 ms 29020 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 5 ms 29164 KB Output is correct
5 Correct 4 ms 29184 KB Output is correct
6 Correct 4 ms 29160 KB Output is correct
7 Correct 5 ms 29020 KB Output is correct
8 Correct 5 ms 29192 KB Output is correct
9 Correct 4 ms 29168 KB Output is correct
10 Correct 5 ms 29016 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 5 ms 29168 KB Output is correct
13 Correct 4 ms 29020 KB Output is correct
14 Correct 4 ms 29220 KB Output is correct
15 Correct 4 ms 29020 KB Output is correct
16 Correct 5 ms 29164 KB Output is correct
17 Correct 5 ms 29020 KB Output is correct
18 Correct 6 ms 29784 KB Output is correct
19 Correct 7 ms 29788 KB Output is correct
20 Correct 8 ms 29788 KB Output is correct
21 Correct 8 ms 29788 KB Output is correct
22 Correct 7 ms 29788 KB Output is correct
23 Correct 7 ms 29788 KB Output is correct
24 Correct 7 ms 29788 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 5 ms 29164 KB Output is correct
5 Correct 4 ms 29184 KB Output is correct
6 Correct 4 ms 29160 KB Output is correct
7 Correct 5 ms 29020 KB Output is correct
8 Correct 5 ms 29192 KB Output is correct
9 Correct 4 ms 29168 KB Output is correct
10 Correct 5 ms 29016 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 5 ms 29168 KB Output is correct
13 Correct 4 ms 29020 KB Output is correct
14 Correct 4 ms 29220 KB Output is correct
15 Correct 4 ms 29020 KB Output is correct
16 Correct 5 ms 29164 KB Output is correct
17 Correct 5 ms 29020 KB Output is correct
18 Correct 6 ms 29784 KB Output is correct
19 Correct 7 ms 29788 KB Output is correct
20 Correct 8 ms 29788 KB Output is correct
21 Correct 8 ms 29788 KB Output is correct
22 Correct 7 ms 29788 KB Output is correct
23 Correct 7 ms 29788 KB Output is correct
24 Correct 7 ms 29788 KB Output is correct
25 Correct 5 ms 29164 KB Output is correct
26 Correct 7 ms 29788 KB Output is correct
27 Correct 7 ms 29788 KB Output is correct
28 Correct 7 ms 29788 KB Output is correct
29 Correct 7 ms 29808 KB Output is correct
30 Correct 8 ms 29532 KB Output is correct
31 Correct 8 ms 29596 KB Output is correct
32 Correct 8 ms 29528 KB Output is correct
33 Correct 7 ms 29372 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 5 ms 29164 KB Output is correct
5 Correct 4 ms 29184 KB Output is correct
6 Correct 4 ms 29160 KB Output is correct
7 Correct 5 ms 29020 KB Output is correct
8 Correct 5 ms 29192 KB Output is correct
9 Correct 4 ms 29168 KB Output is correct
10 Correct 5 ms 29016 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 5 ms 29168 KB Output is correct
13 Correct 4 ms 29020 KB Output is correct
14 Correct 4 ms 29220 KB Output is correct
15 Correct 4 ms 29020 KB Output is correct
16 Correct 5 ms 29164 KB Output is correct
17 Correct 5 ms 29020 KB Output is correct
18 Correct 6 ms 29784 KB Output is correct
19 Correct 7 ms 29788 KB Output is correct
20 Correct 8 ms 29788 KB Output is correct
21 Correct 8 ms 29788 KB Output is correct
22 Correct 7 ms 29788 KB Output is correct
23 Correct 7 ms 29788 KB Output is correct
24 Correct 7 ms 29788 KB Output is correct
25 Incorrect 103 ms 62916 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 5 ms 29016 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 122 ms 43848 KB Output is correct
4 Correct 133 ms 43840 KB Output is correct
5 Correct 126 ms 43972 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 5 ms 29164 KB Output is correct
5 Correct 4 ms 29184 KB Output is correct
6 Correct 4 ms 29160 KB Output is correct
7 Correct 5 ms 29020 KB Output is correct
8 Correct 5 ms 29192 KB Output is correct
9 Correct 4 ms 29168 KB Output is correct
10 Correct 5 ms 29016 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 5 ms 29168 KB Output is correct
13 Correct 4 ms 29020 KB Output is correct
14 Correct 4 ms 29220 KB Output is correct
15 Correct 4 ms 29020 KB Output is correct
16 Correct 5 ms 29164 KB Output is correct
17 Correct 5 ms 29020 KB Output is correct
18 Correct 6 ms 29784 KB Output is correct
19 Correct 7 ms 29788 KB Output is correct
20 Correct 8 ms 29788 KB Output is correct
21 Correct 8 ms 29788 KB Output is correct
22 Correct 7 ms 29788 KB Output is correct
23 Correct 7 ms 29788 KB Output is correct
24 Correct 7 ms 29788 KB Output is correct
25 Correct 5 ms 29164 KB Output is correct
26 Correct 7 ms 29788 KB Output is correct
27 Correct 7 ms 29788 KB Output is correct
28 Correct 7 ms 29788 KB Output is correct
29 Correct 7 ms 29808 KB Output is correct
30 Correct 8 ms 29532 KB Output is correct
31 Correct 8 ms 29596 KB Output is correct
32 Correct 8 ms 29528 KB Output is correct
33 Correct 7 ms 29372 KB Output is correct
34 Incorrect 103 ms 62916 KB Output isn't correct
35 Halted 0 ms 0 KB -