oj.uz

Submission #961671

# Submission time Handle Problem Language Result Execution time Memory
961671 2024-04-12T10:04:41 Z ThylOne Cat Exercise (JOI23_ho_t4) C++14
54 / 100
 264 ms 53072 KB 
//####################
//CatExercise
//####################
#include<bits/stdc++.h>

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 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7060 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 2 ms 7000 KB Output is correct
8 Correct 1 ms 6920 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7060 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 2 ms 7000 KB Output is correct
8 Correct 1 ms 6920 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7000 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 2 ms 7004 KB Output is correct
16 Correct 3 ms 7004 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 6 ms 9564 KB Output is correct
19 Correct 6 ms 9648 KB Output is correct
20 Correct 6 ms 9680 KB Output is correct
21 Correct 5 ms 9560 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 5 ms 9564 KB Output is correct
24 Correct 6 ms 9564 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7060 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 2 ms 7000 KB Output is correct
8 Correct 1 ms 6920 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7000 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 2 ms 7004 KB Output is correct
16 Correct 3 ms 7004 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 6 ms 9564 KB Output is correct
19 Correct 6 ms 9648 KB Output is correct
20 Correct 6 ms 9680 KB Output is correct
21 Correct 5 ms 9560 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 5 ms 9564 KB Output is correct
24 Correct 6 ms 9564 KB Output is correct
25 Correct 2 ms 7004 KB Output is correct
26 Correct 5 ms 9560 KB Output is correct
27 Correct 5 ms 9564 KB Output is correct
28 Correct 5 ms 9564 KB Output is correct
29 Correct 5 ms 9560 KB Output is correct
30 Correct 6 ms 9308 KB Output is correct
31 Correct 6 ms 9380 KB Output is correct
32 Correct 5 ms 9304 KB Output is correct
33 Correct 6 ms 9560 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7060 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 2 ms 7000 KB Output is correct
8 Correct 1 ms 6920 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7000 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 2 ms 7004 KB Output is correct
16 Correct 3 ms 7004 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 6 ms 9564 KB Output is correct
19 Correct 6 ms 9648 KB Output is correct
20 Correct 6 ms 9680 KB Output is correct
21 Correct 5 ms 9560 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 5 ms 9564 KB Output is correct
24 Correct 6 ms 9564 KB Output is correct
25 Incorrect 220 ms 53072 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 1 ms 7000 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 264 ms 49688 KB Output is correct
4 Correct 256 ms 49464 KB Output is correct
5 Correct 258 ms 49320 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7060 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 2 ms 7000 KB Output is correct
8 Correct 1 ms 6920 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7000 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 2 ms 7004 KB Output is correct
16 Correct 3 ms 7004 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 6 ms 9564 KB Output is correct
19 Correct 6 ms 9648 KB Output is correct
20 Correct 6 ms 9680 KB Output is correct
21 Correct 5 ms 9560 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 5 ms 9564 KB Output is correct
24 Correct 6 ms 9564 KB Output is correct
25 Correct 2 ms 7004 KB Output is correct
26 Correct 5 ms 9560 KB Output is correct
27 Correct 5 ms 9564 KB Output is correct
28 Correct 5 ms 9564 KB Output is correct
29 Correct 5 ms 9560 KB Output is correct
30 Correct 6 ms 9308 KB Output is correct
31 Correct 6 ms 9380 KB Output is correct
32 Correct 5 ms 9304 KB Output is correct
33 Correct 6 ms 9560 KB Output is correct
34 Incorrect 220 ms 53072 KB Output isn't correct
35 Halted 0 ms 0 KB -