oj.uz

Submission #961675

# Submission time Handle Problem Language Result Execution time Memory
961675 2024-04-12T10:06:34 Z ThylOne Cat Exercise (JOI23_ho_t4) C++14
100 / 100
 300 ms 59516 KB 
//####################
//CatExercise
//####################
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxiN = 200001;
vector<int> links[maxiN];
int dp[maxiN];
const int LOG = 20;
int depth[maxiN];
long long up[maxiN][LOG];
void dfs(int node,int papa=-1,int deep=0){
    up[node][0] = papa;
    depth[node] = deep;
    for(int v:links[node]){
        if(papa==v)continue;
        dfs(v,node,deep+1);
    }
}
void computeUp(int n){
    for(int l=1;l<LOG;l++){
        for(int i = 0;i<n;i++){
            if(up[i][l-1]==-1){
                up[i][l]=-1;
            }else{
                up[i][l] = up[up[i][l-1]][l-1];
            }
        }
    }
}
int jumpK(int a,int k){
    for(int l=0;l<LOG;l++){
        if((k>>l)&1){
            a = up[a][l];
        }
    }
    return a;
}
int lca(int a,int b){
    if(depth[a]<depth[b])swap(a,b);
    a = jumpK(a,depth[a]-depth[b]);
   
    if(a==b){
        return b;
    }
    for(int l=LOG-1;l>=0;l--){
        if(up[a][l]!=up[b][l]){
            a=up[a][l];
            b=up[b][l];
        }
    }
    return up[a][0];
}
int dist(int a,int b){
    int LCA = lca(a,b);
    return depth[a]+depth[b]-2*depth[LCA];
}
struct UnionFind{
    vector<int> chef;
    void init(int n){
        chef.resize(n);
        for(int i=0;i<n;i++){
            chef[i]=i;
        }
    }
    int find(int a){
        if(a==chef[a])return a;
        else return chef[a]=find(chef[a]);
    }
    void enraciner(int x,int r){
        if(find(x)==find(r)){
            return;
        }else{
            int fx = find(x);
            int fy = find(r);
            chef[fx] = fy;
        }
    }
};
signed main(){
    
    int n;cin>>n;
    int powers[n];
    for(int i = 0;i<n;i++){
        dp[i]=0;
        cin>>powers[i];
        powers[i]--;
    }
    for(int i= 0;i<n-1;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        links[powers[a]].push_back(powers[b]);
        links[powers[b]].push_back(powers[a]);
    }
    dfs(0);
    computeUp(n);
    UnionFind UF;
    UF.init(n);
    for(int i = 0; i < n ; i++){
        dp[i] = 0;
        for(int voisin:links[i]){
            if(voisin>i)continue;
            int rep = UF.find(voisin); 
            dp[i] = max(dp[i], dp[rep]+dist(i,rep));
            UF.enraciner(voisin,i);
        }
    }
    cout<<dp[n-1]<<endl;
    
    return 0;
};

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 3 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 3 ms 8540 KB Output is correct
12 Correct 3 ms 8536 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 3 ms 8540 KB Output is correct
17 Correct 2 ms 8536 KB Output is correct
18 Correct 7 ms 11100 KB Output is correct
19 Correct 7 ms 11100 KB Output is correct
20 Correct 6 ms 11096 KB Output is correct
21 Correct 6 ms 11100 KB Output is correct
22 Correct 6 ms 11100 KB Output is correct
23 Correct 7 ms 11352 KB Output is correct
24 Correct 6 ms 11100 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 3 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 3 ms 8540 KB Output is correct
12 Correct 3 ms 8536 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 3 ms 8540 KB Output is correct
17 Correct 2 ms 8536 KB Output is correct
18 Correct 7 ms 11100 KB Output is correct
19 Correct 7 ms 11100 KB Output is correct
20 Correct 6 ms 11096 KB Output is correct
21 Correct 6 ms 11100 KB Output is correct
22 Correct 6 ms 11100 KB Output is correct
23 Correct 7 ms 11352 KB Output is correct
24 Correct 6 ms 11100 KB Output is correct
25 Correct 2 ms 8540 KB Output is correct
26 Correct 6 ms 11100 KB Output is correct
27 Correct 6 ms 11100 KB Output is correct
28 Correct 6 ms 11100 KB Output is correct
29 Correct 7 ms 11100 KB Output is correct
30 Correct 6 ms 11100 KB Output is correct
31 Correct 7 ms 10932 KB Output is correct
32 Correct 7 ms 11100 KB Output is correct
33 Correct 6 ms 11096 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 3 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 3 ms 8540 KB Output is correct
12 Correct 3 ms 8536 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 3 ms 8540 KB Output is correct
17 Correct 2 ms 8536 KB Output is correct
18 Correct 7 ms 11100 KB Output is correct
19 Correct 7 ms 11100 KB Output is correct
20 Correct 6 ms 11096 KB Output is correct
21 Correct 6 ms 11100 KB Output is correct
22 Correct 6 ms 11100 KB Output is correct
23 Correct 7 ms 11352 KB Output is correct
24 Correct 6 ms 11100 KB Output is correct
25 Correct 212 ms 52052 KB Output is correct
26 Correct 211 ms 59336 KB Output is correct
27 Correct 207 ms 59516 KB Output is correct
28 Correct 274 ms 58972 KB Output is correct
29 Correct 263 ms 56348 KB Output is correct
30 Correct 265 ms 58196 KB Output is correct
31 Correct 260 ms 57368 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 277 ms 50360 KB Output is correct
4 Correct 262 ms 50472 KB Output is correct
5 Correct 249 ms 50516 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 3 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 3 ms 8540 KB Output is correct
12 Correct 3 ms 8536 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 3 ms 8540 KB Output is correct
17 Correct 2 ms 8536 KB Output is correct
18 Correct 7 ms 11100 KB Output is correct
19 Correct 7 ms 11100 KB Output is correct
20 Correct 6 ms 11096 KB Output is correct
21 Correct 6 ms 11100 KB Output is correct
22 Correct 6 ms 11100 KB Output is correct
23 Correct 7 ms 11352 KB Output is correct
24 Correct 6 ms 11100 KB Output is correct
25 Correct 2 ms 8540 KB Output is correct
26 Correct 6 ms 11100 KB Output is correct
27 Correct 6 ms 11100 KB Output is correct
28 Correct 6 ms 11100 KB Output is correct
29 Correct 7 ms 11100 KB Output is correct
30 Correct 6 ms 11100 KB Output is correct
31 Correct 7 ms 10932 KB Output is correct
32 Correct 7 ms 11100 KB Output is correct
33 Correct 6 ms 11096 KB Output is correct
34 Correct 212 ms 52052 KB Output is correct
35 Correct 211 ms 59336 KB Output is correct
36 Correct 207 ms 59516 KB Output is correct
37 Correct 274 ms 58972 KB Output is correct
38 Correct 263 ms 56348 KB Output is correct
39 Correct 265 ms 58196 KB Output is correct
40 Correct 260 ms 57368 KB Output is correct
41 Correct 2 ms 8540 KB Output is correct
42 Correct 2 ms 8540 KB Output is correct
43 Correct 277 ms 50360 KB Output is correct
44 Correct 262 ms 50472 KB Output is correct
45 Correct 249 ms 50516 KB Output is correct
46 Correct 236 ms 57808 KB Output is correct
47 Correct 247 ms 57884 KB Output is correct
48 Correct 227 ms 57804 KB Output is correct
49 Correct 222 ms 57756 KB Output is correct
50 Correct 283 ms 53532 KB Output is correct
51 Correct 284 ms 53588 KB Output is correct
52 Correct 300 ms 53772 KB Output is correct
53 Correct 299 ms 53552 KB Output is correct