oj.uz

Submission #851171

# Submission time Handle Problem Language Result Execution time Memory
851171 2023-09-18T17:41:06 Z Charizard2021 Cat Exercise (JOI23_ho_t4) C++17
21 / 100
 2000 ms 50568 KB 
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);; cin.tie(NULL)
const int N = 200001;
vector<int> adj[N];
vector<int> depth(N);
int parents[N][18];
vector<int> parent(N);
vector<int> maxVal(N);
vector<int> h(N);
vector<int> sz(N);
void dfs(int u){
    for(int v : adj[u]){
        if(v != parents[u][0]){
            parents[v][0] = u;
            depth[v] = depth[u] + 1;
            dfs(v);
        }
    }
}
int distance(int a, int b){
    int dist = depth[a] + depth[b];
    if(depth[a] < depth[b]){
        swap(a, b);
    }
    int diff = depth[a] - depth[b];
    int val = 0;
    while(diff > 0){
        if(diff & 1){
            a = parents[a][val];
        }
        diff /= 2;
        val++;
    }
    if(a == b){
        return dist - 2 * depth[a];
    }
    for(int i = 17; i >= 0; i++){
        if(parents[a][i] != parents[b][i]){
            a = parents[a][i];
            b = parents[b][i];
        }
    }
    return dist - 2 * depth[a] + 2;
}
int getRoot(int u){
    if(parent[u] == u){
        return u;
    }
    return parent[u] = getRoot(parent[u]);
}
void unite(int a, int b){
    int u = getRoot(a);
    int v = getRoot(b);
    if(u == v){
        return;
    }
    if(sz[u] == sz[v]){
        sz[u]++;
    }
    if(sz[u] > sz[v]){
        parent[v] = u;
        if(h[maxVal[v]] > h[maxVal[u]]){
            maxVal[u] = maxVal[v];
        }
    }
    else{
        parent[u] = v;
        if(h[maxVal[u]] > h[maxVal[v]]){
            maxVal[v] = maxVal[u];
        }
    }
}
int main(){
    IOS;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    parents[1][0] = 1;
    dfs(1);
    for(int j = 1; j <= 17; j++){
        for(int i = 1; i <= n; i++){
            parents[i][j] = parents[parents[i][j - 1]][j - 1];
        }
    }
    for(int i = 1; i <= n; i++){
        parent[i] = i;
        maxVal[i] = i;
    }
    vector<pair<int, int> > adj2[1 + n];
    vector<pair<int, int> > positions(1 + n);
    for(int i = 1; i <= n; i++){
        positions[i] = make_pair(h[i], i);
    }
    sort(positions.begin(), positions.end());
    for(int i = 1; i <= n; i++){
        int u = positions[i].second;
        for(int v : adj[u]){
            if(h[v] <= h[u]){
                int weight = maxVal[getRoot(v)];
                adj2[u].push_back(make_pair(weight, distance(u, weight)));
                unite(u, v);
            }
        }
    }
    vector<int> dist(1 + n);
    vector<bool> visited(1 + n, false);
    queue<int> q;
    q.push(positions[n].second);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        visited[u] = true;
        for(pair<int, int> x : adj2[u]){
            int v = x.first;
            if(!visited[v]){
                visited[v] = true;
                dist[v] = dist[u] + x.second;
                q.push(v);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, dist[i]);
    }
    cout << ans << "\n";
}

Compilation message

Main.cpp: In function 'int distance(int, int)':
Main.cpp:38:5: warning: iteration 2147483630 invokes undefined behavior [-Waggressive-loop-optimizations]
   38 |     for(int i = 17; i >= 0; i++){
      |     ^~~
Main.cpp:38:23: note: within this loop
   38 |     for(int i = 17; i >= 0; i++){
      |                     ~~^~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10584 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 4 ms 10680 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 3 ms 10588 KB Output is correct
10 Correct 3 ms 10588 KB Output is correct
11 Correct 3 ms 10584 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 3 ms 10588 KB Output is correct
14 Correct 3 ms 10588 KB Output is correct
15 Correct 3 ms 10588 KB Output is correct
16 Correct 3 ms 10588 KB Output is correct
17 Correct 3 ms 10588 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10584 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 4 ms 10680 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 3 ms 10588 KB Output is correct
10 Correct 3 ms 10588 KB Output is correct
11 Correct 3 ms 10584 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 3 ms 10588 KB Output is correct
14 Correct 3 ms 10588 KB Output is correct
15 Correct 3 ms 10588 KB Output is correct
16 Correct 3 ms 10588 KB Output is correct
17 Correct 3 ms 10588 KB Output is correct
18 Correct 7 ms 13400 KB Output is correct
19 Correct 5 ms 13400 KB Output is correct
20 Correct 5 ms 13604 KB Output is correct
21 Correct 5 ms 13404 KB Output is correct
22 Correct 5 ms 13364 KB Output is correct
23 Correct 5 ms 13404 KB Output is correct
24 Correct 5 ms 13404 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10584 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 4 ms 10680 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 3 ms 10588 KB Output is correct
10 Correct 3 ms 10588 KB Output is correct
11 Correct 3 ms 10584 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 3 ms 10588 KB Output is correct
14 Correct 3 ms 10588 KB Output is correct
15 Correct 3 ms 10588 KB Output is correct
16 Correct 3 ms 10588 KB Output is correct
17 Correct 3 ms 10588 KB Output is correct
18 Correct 7 ms 13400 KB Output is correct
19 Correct 5 ms 13400 KB Output is correct
20 Correct 5 ms 13604 KB Output is correct
21 Correct 5 ms 13404 KB Output is correct
22 Correct 5 ms 13364 KB Output is correct
23 Correct 5 ms 13404 KB Output is correct
24 Correct 5 ms 13404 KB Output is correct
25 Execution timed out 2075 ms 10588 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10584 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 4 ms 10680 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 3 ms 10588 KB Output is correct
10 Correct 3 ms 10588 KB Output is correct
11 Correct 3 ms 10584 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 3 ms 10588 KB Output is correct
14 Correct 3 ms 10588 KB Output is correct
15 Correct 3 ms 10588 KB Output is correct
16 Correct 3 ms 10588 KB Output is correct
17 Correct 3 ms 10588 KB Output is correct
18 Correct 7 ms 13400 KB Output is correct
19 Correct 5 ms 13400 KB Output is correct
20 Correct 5 ms 13604 KB Output is correct
21 Correct 5 ms 13404 KB Output is correct
22 Correct 5 ms 13364 KB Output is correct
23 Correct 5 ms 13404 KB Output is correct
24 Correct 5 ms 13404 KB Output is correct
25 Incorrect 110 ms 50568 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2017 ms 10584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10584 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 4 ms 10680 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 3 ms 10588 KB Output is correct
10 Correct 3 ms 10588 KB Output is correct
11 Correct 3 ms 10584 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 3 ms 10588 KB Output is correct
14 Correct 3 ms 10588 KB Output is correct
15 Correct 3 ms 10588 KB Output is correct
16 Correct 3 ms 10588 KB Output is correct
17 Correct 3 ms 10588 KB Output is correct
18 Correct 7 ms 13400 KB Output is correct
19 Correct 5 ms 13400 KB Output is correct
20 Correct 5 ms 13604 KB Output is correct
21 Correct 5 ms 13404 KB Output is correct
22 Correct 5 ms 13364 KB Output is correct
23 Correct 5 ms 13404 KB Output is correct
24 Correct 5 ms 13404 KB Output is correct
25 Execution timed out 2075 ms 10588 KB Time limit exceeded
26 Halted 0 ms 0 KB -