oj.uz

Submission #965544

# Submission time Handle Problem Language Result Execution time Memory
965544 2024-04-18T20:23:03 Z ttamx Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 110 ms 37848 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=2e5+5;

int n;
int a[N];
vector<int> adj[N];
int pa[N],sz[N],hv[N],lv[N],hd[N];
int ord[N],fa[N],dp[N];

void dfs(int u,int p=0){
    pa[u]=p;
    sz[u]=1;
    lv[u]=lv[p]+1;
    for(auto v:adj[u])if(v!=p){
        dfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[hv[u]])hv[u]=v;
    }
}

void hld(int u,int p=0){
    if(!hd[u])hd[u]=u;
    if(hv[u])hd[hv[u]]=hd[u],hld(hv[u],u);
    for(auto v:adj[u])if(v!=p&&v!=hv[u])hld(v,u);
}

int lca(int u,int v){
    while(hd[u]!=hd[v]){
        if(lv[hd[u]]<lv[hd[v]])swap(u,v);
        u=pa[hd[u]];
    }
    return lv[u]<lv[v]?u:v;
}

int dist(int u,int v){
    return lv[u]+lv[v]-2*lv[lca(u,v)];
}

int fp(int u){
    return fa[u]=fa[u]==u?u:fp(fa[u]);
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<=n;i++)cin >> a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(1);
    hld(1);
    iota(fa+1,fa+n+1,1);
    iota(ord+1,ord+n+1,1);
    sort(ord+1,ord+n+1,[&](int i,int j){
        return a[i]<a[j];
    });
    for(int i=1;i<=n;i++){
        int u=ord[i];
        for(auto v:adj[u])if(a[u]>a[v]){
            v=fp(v);
            dp[u]=max(dp[u],dp[v]+dist(u,v));
            fa[v]=u;
        }
    }
    cout << dp[ord[n]];
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9048 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 2 ms 9188 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9192 KB Output is correct
13 Correct 2 ms 9460 KB Output is correct
14 Correct 2 ms 9048 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9712 KB Output is correct
20 Correct 4 ms 9820 KB Output is correct
21 Correct 4 ms 9908 KB Output is correct
22 Correct 4 ms 9820 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 ms 9820 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9048 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 2 ms 9188 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9192 KB Output is correct
13 Correct 2 ms 9460 KB Output is correct
14 Correct 2 ms 9048 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9712 KB Output is correct
20 Correct 4 ms 9820 KB Output is correct
21 Correct 4 ms 9908 KB Output is correct
22 Correct 4 ms 9820 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 ms 9820 KB Output is correct
25 Correct 2 ms 9048 KB Output is correct
26 Correct 4 ms 9564 KB Output is correct
27 Correct 4 ms 9560 KB Output is correct
28 Correct 4 ms 9564 KB Output is correct
29 Correct 4 ms 9712 KB Output is correct
30 Correct 4 ms 9540 KB Output is correct
31 Correct 4 ms 9308 KB Output is correct
32 Correct 4 ms 9308 KB Output is correct
33 Correct 4 ms 9308 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9048 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 2 ms 9188 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9192 KB Output is correct
13 Correct 2 ms 9460 KB Output is correct
14 Correct 2 ms 9048 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9712 KB Output is correct
20 Correct 4 ms 9820 KB Output is correct
21 Correct 4 ms 9908 KB Output is correct
22 Correct 4 ms 9820 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 ms 9820 KB Output is correct
25 Incorrect 91 ms 37848 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 2 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 110 ms 22096 KB Output is correct
4 Correct 103 ms 21912 KB Output is correct
5 Correct 102 ms 22100 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9048 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 2 ms 9188 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9192 KB Output is correct
13 Correct 2 ms 9460 KB Output is correct
14 Correct 2 ms 9048 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9712 KB Output is correct
20 Correct 4 ms 9820 KB Output is correct
21 Correct 4 ms 9908 KB Output is correct
22 Correct 4 ms 9820 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 ms 9820 KB Output is correct
25 Correct 2 ms 9048 KB Output is correct
26 Correct 4 ms 9564 KB Output is correct
27 Correct 4 ms 9560 KB Output is correct
28 Correct 4 ms 9564 KB Output is correct
29 Correct 4 ms 9712 KB Output is correct
30 Correct 4 ms 9540 KB Output is correct
31 Correct 4 ms 9308 KB Output is correct
32 Correct 4 ms 9308 KB Output is correct
33 Correct 4 ms 9308 KB Output is correct
34 Incorrect 91 ms 37848 KB Output isn't correct
35 Halted 0 ms 0 KB -