oj.uz

답안 #835037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
835037 2023-08-23T06:40:29 Z isaachew Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 244 ms 40836 KB 
#include <bits/stdc++.h>
/*
 When you are at node k, you cannot go to any node > k as that is unreachable
 */
struct dsu{
    std::vector<int> parents;
    std::vector<int> maxes;
    dsu(int n){
        parents.resize(n,-1);
        for(int i=0;i<n;i++){
            maxes.push_back(i);
        }
    }
    void combine(int a,int b){
        a=find(a),b=find(b);
        parents[a]=b;
        maxes[b]=std::max(maxes[a],maxes[b]);
    }
    int find(int x){
        if(parents[x]==-1)return x;
        else{
            return (parents[x]=find(parents[x]));
        }
    }
};
std::vector<std::vector<int>> edges;
std::vector<int> depths;
std::vector<int> parents;
std::vector<std::vector<int>> binlifts;
void dfs(int cur,int parent){
    parents[cur]=parent;
    for(int i:edges[cur]){
        if(i==parent)continue;
        depths[i]=depths[cur]+1;
        dfs(i,cur);
    }
}
int lca(int a,int b){
    if(depths[a]<depths[b])std::swap(a,b);
    for(int i=20;i--;){
        if(depths[a]-(1<<i)>=depths[b]){
            a=binlifts[i][a];
        }
    }
    if(a==b)return a;//a is an ancestor/descendant of b
    for(int i=20;i--;){
        int na=binlifts[i][a],nb=binlifts[i][b];
        if(na!=nb){
            a=na,b=nb;
        }
    }
    return parents[a];
}
int getdist(int a,int b){
    int clca=lca(a,b);
    return depths[a]+depths[b]-2*depths[clca];
}
int main(){
    int n;
    std::cin>>n;
    std::vector<int> theights;
    std::vector<int> scores(n);
    depths.resize(n);
    edges.resize(n);
    binlifts.resize(20);
    parents.resize(n);
    dsu conncs(n);
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        x--;
        theights.push_back(x);
    }
    for(int i=1;i<n;i++){
        int a,b;
        std::cin>>a>>b;
        a=theights[a-1],b=theights[b-1];
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(0,0);
    binlifts[0]=parents;
    for(int i=0;i<19;i++){
        for(int j=0;j<n;j++){
            binlifts[i+1].push_back(binlifts[i][binlifts[i][j]]);
        }
    }
    for(int i=0;i<n;i++){
        int cscore=0;
        for(int j:edges[i]){
            if(j>i)continue;
            int jpcc=conncs.maxes[conncs.find(j)];
            cscore=std::max(cscore,scores[jpcc]+getdist(i,jpcc));
            conncs.combine(i,jpcc);
        }
        scores[i]=cscore;
    }
    std::cout<<scores.back()<<'\n';
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 4 ms 1336 KB Output is correct
19 Correct 5 ms 1492 KB Output is correct
20 Correct 4 ms 1464 KB Output is correct
21 Correct 5 ms 1384 KB Output is correct
22 Correct 5 ms 1364 KB Output is correct
23 Correct 5 ms 1364 KB Output is correct
24 Correct 5 ms 1368 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 4 ms 1336 KB Output is correct
19 Correct 5 ms 1492 KB Output is correct
20 Correct 4 ms 1464 KB Output is correct
21 Correct 5 ms 1384 KB Output is correct
22 Correct 5 ms 1364 KB Output is correct
23 Correct 5 ms 1364 KB Output is correct
24 Correct 5 ms 1368 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 4 ms 1364 KB Output is correct
27 Correct 4 ms 1364 KB Output is correct
28 Correct 5 ms 1364 KB Output is correct
29 Correct 5 ms 1364 KB Output is correct
30 Correct 5 ms 1108 KB Output is correct
31 Correct 5 ms 1108 KB Output is correct
32 Correct 4 ms 1108 KB Output is correct
33 Correct 5 ms 1108 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 4 ms 1336 KB Output is correct
19 Correct 5 ms 1492 KB Output is correct
20 Correct 4 ms 1464 KB Output is correct
21 Correct 5 ms 1384 KB Output is correct
22 Correct 5 ms 1364 KB Output is correct
23 Correct 5 ms 1364 KB Output is correct
24 Correct 5 ms 1368 KB Output is correct
25 Incorrect 193 ms 40836 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 242 ms 36048 KB Output is correct
4 Correct 240 ms 36244 KB Output is correct
5 Correct 244 ms 36156 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 4 ms 1336 KB Output is correct
19 Correct 5 ms 1492 KB Output is correct
20 Correct 4 ms 1464 KB Output is correct
21 Correct 5 ms 1384 KB Output is correct
22 Correct 5 ms 1364 KB Output is correct
23 Correct 5 ms 1364 KB Output is correct
24 Correct 5 ms 1368 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 4 ms 1364 KB Output is correct
27 Correct 4 ms 1364 KB Output is correct
28 Correct 5 ms 1364 KB Output is correct
29 Correct 5 ms 1364 KB Output is correct
30 Correct 5 ms 1108 KB Output is correct
31 Correct 5 ms 1108 KB Output is correct
32 Correct 4 ms 1108 KB Output is correct
33 Correct 5 ms 1108 KB Output is correct
34 Incorrect 193 ms 40836 KB Output isn't correct
35 Halted 0 ms 0 KB -