oj.uz

Submission #935693

# Submission time Handle Problem Language Result Execution time Memory
935693 2024-02-29T11:48:37 Z carriewang Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 186 ms 50276 KB 
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
const int maxn=200005;
int n,a,b,p[maxn][20],h[maxn],dep[maxn],dp[maxn];
vi g[maxn];
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for(int i=0;i<n;i++) cin >> h[i];
    for(int i=1;i<n;i++){
        cin >>  a >> b;
        a--,b--;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    function<void(int,int)> dfs=[&](int x,int pre){
        dep[x]=dep[pre]+1;
        p[x][0]=pre;
        for(int i=1;i<20;i++) p[x][i]=p[p[x][i-1]][i-1];
        for(int u:g[x]){
            if(u==pre) continue;
            dfs(u,x);
        }
    };
    dfs(0,0);
    function<int(int,int)> lca=[&](int x,int y){
        if(dep[x]>dep[y]) swap(x,y);
        int tmp=dep[y]-dep[x],i=0;
        while(tmp){
            if(tmp&1) y=p[y][i];
            i++,tmp>>=1;
        }
        if(x==y) return x;
        for(int j=19;j>=0;j--){
            if(p[x][j]!=p[y][j]){
                x=p[x][j];
                y=p[y][j];
            }
        }
        return p[x][0];
    };
    vi ord(n),pa(n);
    iota(all(ord),0);
    iota(all(pa),0);
    sort(all(ord),[](int i,int j){return h[i]<h[j];});
    function<int(int)> get=[&](int x){
        return x==pa[x] ? x : pa[x]=get(pa[x]);
    };
    function<int(int,int)> get_dist=[&](int x,int y){
        return dep[x]+dep[y]-2*dep[lca(x,y)];
    };
    for(int i:ord){
        for(int j:g[i]){
            if(h[i]>h[j]){
                dp[i]=max(dp[i],dp[get(j)]+get_dist(i,get(j)));
                pa[get(j)]=i;
            }
        }
    }
    cout << dp[ord[n-1]] << "\n";
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8840 KB Output is correct
3 Correct 2 ms 9044 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8792 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8840 KB Output is correct
3 Correct 2 ms 9044 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8792 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 3 ms 8796 KB Output is correct
13 Correct 2 ms 8792 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8840 KB Output is correct
18 Correct 4 ms 9304 KB Output is correct
19 Correct 5 ms 9424 KB Output is correct
20 Correct 5 ms 9360 KB Output is correct
21 Correct 5 ms 9304 KB Output is correct
22 Correct 5 ms 9440 KB Output is correct
23 Correct 5 ms 9308 KB Output is correct
24 Correct 4 ms 9308 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8840 KB Output is correct
3 Correct 2 ms 9044 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8792 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 3 ms 8796 KB Output is correct
13 Correct 2 ms 8792 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8840 KB Output is correct
18 Correct 4 ms 9304 KB Output is correct
19 Correct 5 ms 9424 KB Output is correct
20 Correct 5 ms 9360 KB Output is correct
21 Correct 5 ms 9304 KB Output is correct
22 Correct 5 ms 9440 KB Output is correct
23 Correct 5 ms 9308 KB Output is correct
24 Correct 4 ms 9308 KB Output is correct
25 Correct 2 ms 9048 KB Output is correct
26 Correct 6 ms 9560 KB Output is correct
27 Correct 4 ms 9304 KB Output is correct
28 Correct 5 ms 9052 KB Output is correct
29 Correct 5 ms 9304 KB Output is correct
30 Correct 4 ms 9052 KB Output is correct
31 Correct 4 ms 8908 KB Output is correct
32 Correct 5 ms 9052 KB Output is correct
33 Correct 4 ms 8916 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8840 KB Output is correct
3 Correct 2 ms 9044 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8792 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 3 ms 8796 KB Output is correct
13 Correct 2 ms 8792 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8840 KB Output is correct
18 Correct 4 ms 9304 KB Output is correct
19 Correct 5 ms 9424 KB Output is correct
20 Correct 5 ms 9360 KB Output is correct
21 Correct 5 ms 9304 KB Output is correct
22 Correct 5 ms 9440 KB Output is correct
23 Correct 5 ms 9308 KB Output is correct
24 Correct 4 ms 9308 KB Output is correct
25 Incorrect 131 ms 50276 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 8844 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 172 ms 34656 KB Output is correct
4 Correct 186 ms 34548 KB Output is correct
5 Correct 164 ms 34660 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8840 KB Output is correct
3 Correct 2 ms 9044 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8792 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 3 ms 8796 KB Output is correct
13 Correct 2 ms 8792 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8840 KB Output is correct
18 Correct 4 ms 9304 KB Output is correct
19 Correct 5 ms 9424 KB Output is correct
20 Correct 5 ms 9360 KB Output is correct
21 Correct 5 ms 9304 KB Output is correct
22 Correct 5 ms 9440 KB Output is correct
23 Correct 5 ms 9308 KB Output is correct
24 Correct 4 ms 9308 KB Output is correct
25 Correct 2 ms 9048 KB Output is correct
26 Correct 6 ms 9560 KB Output is correct
27 Correct 4 ms 9304 KB Output is correct
28 Correct 5 ms 9052 KB Output is correct
29 Correct 5 ms 9304 KB Output is correct
30 Correct 4 ms 9052 KB Output is correct
31 Correct 4 ms 8908 KB Output is correct
32 Correct 5 ms 9052 KB Output is correct
33 Correct 4 ms 8916 KB Output is correct
34 Incorrect 131 ms 50276 KB Output isn't correct
35 Halted 0 ms 0 KB -