oj.uz

Submission #769672

# Submission time Handle Problem Language Result Execution time Memory
769672 2023-06-30T02:06:44 Z Ozy Cat Exercise (JOI23_ho_t4) C++17
0 / 100
 2 ms 4948 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);
    }
    if (euler[a].first < euler[b].first && euler[a].second > euler[b].second) x = a;
    else {
        a = anc[a][0];
        res++;
    }

    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
0 / 7.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 23.0

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

Subtask #7
0 / 26.0

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