oj.uz

Submission #935840

# Submission time Handle Problem Language Result Execution time Memory
935840 2024-02-29T16:16:02 Z anton Cat Exercise (JOI23_ho_t4) C++17
41 / 100
 201 ms 29368 KB 
#include<bits/stdc++.h>


using namespace std;
#define int long long
#define pii pair<int, int>
int n;

const int MAX_N = 200000;

vector<int> adj[MAX_N];
int H[MAX_N];
int score[MAX_N];

struct DSU{
    vector<int> dsu;
    vector<int> sz;
    vector<pair<int, pii>> max_v;

    DSU(int len){
        dsu.resize(len);
        sz.resize(len);
        max_v.resize(len);

        for(int i = 0; i<len; i++){
            dsu[i] =i;
            sz[i]= 1;
            max_v[i] = {H[i], {i, 0}};
        }
    }

    int getC(int a){
        if(dsu[a] == a){
            return a;
        }
        int b= getC(dsu[a]);
        dsu[a] = b;
        return b;
    }

    void merge(int a, int b){
        a=getC(a);
        b=getC(b);
        if(sz[a]<sz[b]){
            swap(a, b);
        }
        dsu[b] = a;
        sz[a] += sz[b];
        if(max_v[a].first<max_v[b].first){
            max_v[a] = max_v[b];
        }
    }
};


signed main(){
    cin>>n;

    vector<pii> pts;

    for(int i = 0; i<n; i++){
        cin>>H[i];
        pts.push_back({H[i], i});
    }


    for(int i = 0; i<n-1; i++){
        int a, b;
        cin>>a>>b;
        adj[a-1].push_back(b-1);
        adj[b-1].push_back(a-1);
    }

    sort(pts.begin(), pts.end());

    DSU dsu =DSU(n);
    
    for(int i = 0; i<n; i++){
        int u = pts[i].second;
        int s_after = 0;
        for(auto v: adj[u]){
            if(H[v]<H[u]){
                //cout<<v<<" score "<<dsu.max_v[dsu.getC(v)].first<<" "<<dsu.max_v[dsu.getC(v)].second.first<<" "<<dsu.max_v[dsu.getC(v)].second.second<<endl;
                s_after = max(s_after, dsu.max_v[dsu.getC(v)].second.second + abs(u-dsu.max_v[dsu.getC(v)].second.first));
                //cout<<"merge "<<u<<" "<<v<<endl;
                dsu.merge(u, v);
            }
        }
        dsu.max_v[dsu.getC(u)] = {H[u],{u, s_after}};
        //cout<<u<<" "<<score[u]<<endl;
    }

    cout<<dsu.max_v[dsu.getC(0)].second.second<<endl;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 7856 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8280 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 5 ms 8284 KB Output is correct
19 Correct 5 ms 8540 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8284 KB Output is correct
23 Correct 5 ms 8540 KB Output is correct
24 Correct 5 ms 8308 KB Output is correct
25 Incorrect 2 ms 8028 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 7856 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8280 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 5 ms 8284 KB Output is correct
19 Correct 5 ms 8540 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8284 KB Output is correct
23 Correct 5 ms 8540 KB Output is correct
24 Correct 5 ms 8308 KB Output is correct
25 Correct 169 ms 28692 KB Output is correct
26 Correct 164 ms 29064 KB Output is correct
27 Correct 159 ms 29044 KB Output is correct
28 Correct 193 ms 28864 KB Output is correct
29 Correct 198 ms 29108 KB Output is correct
30 Correct 201 ms 28992 KB Output is correct
31 Correct 184 ms 29368 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 7856 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8280 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 5 ms 8284 KB Output is correct
19 Correct 5 ms 8540 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8284 KB Output is correct
23 Correct 5 ms 8540 KB Output is correct
24 Correct 5 ms 8308 KB Output is correct
25 Incorrect 2 ms 8028 KB Output isn't correct
26 Halted 0 ms 0 KB -