oj.uz

Submission #769671

# Submission time Handle Problem Language Result Execution time Memory
769671 2023-06-30T01:46:45 Z Ozy Cat Exercise (JOI23_ho_t4) C++17
41 / 100
 209 ms 69788 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define lli long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 200000
//para el orden
#define id second

lli n,raiz,a,b,cont;
lli alt[MAX+2],anc[MAX+2][22];
vector<lli> hijos[MAX+2];
pll euler[MAX+2];
vector<pll> orden;
lli dp[MAX+2],uf[MAX+2];

lli sube(lli pos) {
    if (uf[pos] == pos) return pos;
    uf[pos] = sube(uf[pos]);
    return uf[pos];
}

void dfs(lli pos, lli padre) {

    anc[pos][0] = padre;
    rep(i,1,20) {
        anc[pos][i] = anc[padre][i-1];
        padre = anc[pos][i];
    }

    padre = anc[pos][0];
    euler[pos].first = cont++;
    for(auto h : hijos[pos]) {
        if (h==padre) continue;
        dfs(h,pos);
    }
    euler[pos].second = cont;
}

lli dis(lli a, lli b) {

    lli x,res = 0;
    repa(i,20,0) {
        x = anc[a][i];
        if (x == 0) continue;
        if (euler[x].first < euler[b].first && euler[x].second >= euler[b].second) continue;
        a = x;
        res += (1<<i);
    }
    repa(i,20,0) {
        x = anc[b][i];
        if (x == 0) continue;
        if (euler[x].first < euler[a].first && euler[x].second >= euler[a].second) continue;
        b = x;
        res += (1<<i);
    }
    return res;
}

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

    cin >> n;
    rep(i,1,n) {
        cin >> alt[i];
        if (alt[i] == n) raiz = i;
        orden.push_back({alt[i],i});
    }

    rep(i,1,n-1) {
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
    }

    //crea el lca
    cont = 1;
    dfs(raiz,0);

    //empieza con el union find
    sort(orden.begin(), orden.end());
    rep(i,1,n) uf[i] = i;

    for (auto act : orden) {

        for (auto h : hijos[act.id]) {
            if (alt[h] > act.first) continue;

            b = sube(h);
            a = dis(act.id,b) + dp[b];
            dp[act.id] = max(dp[act.id], a);
            uf[b] = act.id;
        }

    }

    cout << dp[raiz];

    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5044 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5044 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5044 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 2 ms 5044 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5040 KB Output is correct
15 Correct 2 ms 5076 KB Output is correct
16 Correct 2 ms 5076 KB Output is correct
17 Correct 3 ms 5048 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5044 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5044 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5044 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 2 ms 5044 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5040 KB Output is correct
15 Correct 2 ms 5076 KB Output is correct
16 Correct 2 ms 5076 KB Output is correct
17 Correct 3 ms 5048 KB Output is correct
18 Correct 5 ms 6612 KB Output is correct
19 Correct 5 ms 6596 KB Output is correct
20 Correct 7 ms 6612 KB Output is correct
21 Correct 6 ms 6612 KB Output is correct
22 Correct 6 ms 6484 KB Output is correct
23 Correct 5 ms 6464 KB Output is correct
24 Correct 5 ms 6464 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5044 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5044 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5044 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 2 ms 5044 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5040 KB Output is correct
15 Correct 2 ms 5076 KB Output is correct
16 Correct 2 ms 5076 KB Output is correct
17 Correct 3 ms 5048 KB Output is correct
18 Correct 5 ms 6612 KB Output is correct
19 Correct 5 ms 6596 KB Output is correct
20 Correct 7 ms 6612 KB Output is correct
21 Correct 6 ms 6612 KB Output is correct
22 Correct 6 ms 6484 KB Output is correct
23 Correct 5 ms 6464 KB Output is correct
24 Correct 5 ms 6464 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 5 ms 6600 KB Output is correct
27 Correct 5 ms 6484 KB Output is correct
28 Correct 5 ms 6612 KB Output is correct
29 Correct 6 ms 6600 KB Output is correct
30 Incorrect 6 ms 6356 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5044 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5044 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5044 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 2 ms 5044 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5040 KB Output is correct
15 Correct 2 ms 5076 KB Output is correct
16 Correct 2 ms 5076 KB Output is correct
17 Correct 3 ms 5048 KB Output is correct
18 Correct 5 ms 6612 KB Output is correct
19 Correct 5 ms 6596 KB Output is correct
20 Correct 7 ms 6612 KB Output is correct
21 Correct 6 ms 6612 KB Output is correct
22 Correct 6 ms 6484 KB Output is correct
23 Correct 5 ms 6464 KB Output is correct
24 Correct 5 ms 6464 KB Output is correct
25 Correct 191 ms 68280 KB Output is correct
26 Correct 151 ms 69720 KB Output is correct
27 Correct 174 ms 69788 KB Output is correct
28 Correct 209 ms 67364 KB Output is correct
29 Correct 204 ms 68504 KB Output is correct
30 Correct 205 ms 68296 KB Output is correct
31 Correct 204 ms 68868 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5044 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5044 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5044 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 2 ms 5044 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5040 KB Output is correct
15 Correct 2 ms 5076 KB Output is correct
16 Correct 2 ms 5076 KB Output is correct
17 Correct 3 ms 5048 KB Output is correct
18 Correct 5 ms 6612 KB Output is correct
19 Correct 5 ms 6596 KB Output is correct
20 Correct 7 ms 6612 KB Output is correct
21 Correct 6 ms 6612 KB Output is correct
22 Correct 6 ms 6484 KB Output is correct
23 Correct 5 ms 6464 KB Output is correct
24 Correct 5 ms 6464 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 5 ms 6600 KB Output is correct
27 Correct 5 ms 6484 KB Output is correct
28 Correct 5 ms 6612 KB Output is correct
29 Correct 6 ms 6600 KB Output is correct
30 Incorrect 6 ms 6356 KB Output isn't correct
31 Halted 0 ms 0 KB -