oj.uz

Submission #1094915

# Submission time Handle Problem Language Result Execution time Memory
1094915 2024-09-30T20:46:59 Z Nom_mxmx Cat Exercise (JOI23_ho_t4) C++14
54 / 100
 153 ms 43988 KB 
#include <bits/stdc++.h>
using namespace std;

#define nl '\n'
#define pb push_back

const int N = 2e5+3;
vector<int> g[N];
int w[N];
int p[N];
int d[N];
int rep[N];
int mx[N];
int dp[N];
int jmp[N][20];

int Find(int a) {
    return (rep[a] == a)? a : rep[a] = Find(rep[a]);
}

void Union(int a, int b) {
    a = Find(a), b = Find(b);
    rep[b] = a;
}

void dfs(int v, int p) {
    d[v] = d[p]+1;
    jmp[v][0] = p;

    for(int i=1; i<20; i++)
        jmp[v][i] = jmp[jmp[v][i-1]][i-1];

    for(auto u:g[v]) {
        if(u == p) continue;
        dfs(u, v);
    }
}

int lca(int a, int b) {
    if(d[a] < d[b]) swap(a, b);

    for(int i=19; i>=0; i--) {
        if(d[jmp[a][i]] >= d[b])
            a = jmp[a][i];
    }
    for(int i=19; i>=0; i--) {
        if(jmp[a][i] != jmp[b][i]) {
            a = jmp[a][i];
            b = jmp[b][i];
        }
    }
    if(a == b) return a;
    return jmp[a][0];
}

int dist(int a, int b) {
    return d[a] + d[b] - 2*d[lca(a, b)];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for(int i=1; i<=n; i++) {
        cin >> w[i];
        p[w[i]] = i;
        rep[i] = i;
    }

    for(int i=1; i<n; i++) {
        int a, b;
        cin >> a >> b;

        g[a].pb(b);
        g[b].pb(a);
    }

    dfs(1, 0);
    for(int i=1; i<=n; i++) {
        int v = p[i];

        for(auto u:g[v]) {
            if(w[v] > w[u]) {
                int a = Find(u);

                dp[v] = max(dp[v], dp[a] + dist(v, a));
                Union(v, a); // v > a 
            }
        }
    }

    cout << dp[p[n]];
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5168 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5168 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 2 ms 4996 KB Output is correct
15 Correct 2 ms 5208 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5168 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 2 ms 4996 KB Output is correct
15 Correct 2 ms 5208 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 5 ms 5980 KB Output is correct
19 Correct 5 ms 6060 KB Output is correct
20 Correct 4 ms 5980 KB Output is correct
21 Correct 4 ms 5980 KB Output is correct
22 Correct 4 ms 5980 KB Output is correct
23 Correct 4 ms 5980 KB Output is correct
24 Correct 4 ms 5980 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5168 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 2 ms 4996 KB Output is correct
15 Correct 2 ms 5208 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 5 ms 5980 KB Output is correct
19 Correct 5 ms 6060 KB Output is correct
20 Correct 4 ms 5980 KB Output is correct
21 Correct 4 ms 5980 KB Output is correct
22 Correct 4 ms 5980 KB Output is correct
23 Correct 4 ms 5980 KB Output is correct
24 Correct 4 ms 5980 KB Output is correct
25 Correct 2 ms 4956 KB Output is correct
26 Correct 4 ms 5944 KB Output is correct
27 Correct 5 ms 5976 KB Output is correct
28 Correct 5 ms 5944 KB Output is correct
29 Correct 5 ms 5980 KB Output is correct
30 Correct 5 ms 5720 KB Output is correct
31 Correct 7 ms 5720 KB Output is correct
32 Correct 4 ms 5724 KB Output is correct
33 Correct 5 ms 5720 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5168 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 2 ms 4996 KB Output is correct
15 Correct 2 ms 5208 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 5 ms 5980 KB Output is correct
19 Correct 5 ms 6060 KB Output is correct
20 Correct 4 ms 5980 KB Output is correct
21 Correct 4 ms 5980 KB Output is correct
22 Correct 4 ms 5980 KB Output is correct
23 Correct 4 ms 5980 KB Output is correct
24 Correct 4 ms 5980 KB Output is correct
25 Incorrect 100 ms 43988 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 4952 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 153 ms 34440 KB Output is correct
4 Correct 142 ms 34436 KB Output is correct
5 Correct 135 ms 34424 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5168 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 2 ms 4996 KB Output is correct
15 Correct 2 ms 5208 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 5 ms 5980 KB Output is correct
19 Correct 5 ms 6060 KB Output is correct
20 Correct 4 ms 5980 KB Output is correct
21 Correct 4 ms 5980 KB Output is correct
22 Correct 4 ms 5980 KB Output is correct
23 Correct 4 ms 5980 KB Output is correct
24 Correct 4 ms 5980 KB Output is correct
25 Correct 2 ms 4956 KB Output is correct
26 Correct 4 ms 5944 KB Output is correct
27 Correct 5 ms 5976 KB Output is correct
28 Correct 5 ms 5944 KB Output is correct
29 Correct 5 ms 5980 KB Output is correct
30 Correct 5 ms 5720 KB Output is correct
31 Correct 7 ms 5720 KB Output is correct
32 Correct 4 ms 5724 KB Output is correct
33 Correct 5 ms 5720 KB Output is correct
34 Incorrect 100 ms 43988 KB Output isn't correct
35 Halted 0 ms 0 KB -