oj.uz

Submission #996625

# Submission time Handle Problem Language Result Execution time Memory
996625 2024-06-11T00:38:28 Z juliany2 Mergers (JOI19_mergers) C++17
0 / 100
 36 ms 30548 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 5e5 + 7, L = 20;
int n, k;
vector<int> adj[N];
int c[N], dep[N];
int lift[N][L];
int l[N], cum[N];
int cnt, r;
bool seen[N];

void prep(int v = 1, int p = 0) {
    lift[v][0] = p;
    for (int i = 1; i < L; i++)
        lift[v][i] = lift[lift[v][i - 1]][i - 1];

    for (int u : adj[v]) {
        if (u == p)
            continue;

        dep[u] = dep[v] + 1;
        prep(u, v);
    }
}

int lca(int u, int v) {
    if (u == 0 || v == 0)
        return max(u, v);

    if (dep[u] > dep[v])
        swap(u, v);

    for (int i = 0; i < L; i++)
        if ((dep[v] - dep[u]) >> i & 1)
            v = lift[v][i];

    if (u == v)
        return u;

    for (int i = L - 1; i >= 0; i--)
        if (lift[v][i] != lift[u][i])
            v = lift[v][i], u = lift[u][i];

    return lift[u][0];
}

void run(int v = 1, int p = 0) {
    for (int u : adj[v]) {
        if (u == p)
            continue;

        run(u, v);
        cum[v] += cum[u];
    }
}

void dfs(int v = 1, int p = 0) {
    for (int u : adj[v]) {
        if (u == p)
            continue;

        dfs(u, v);
        seen[v] |= seen[u];
    }

    if (v != 1 && !cum[v] && !seen[v]) {
        cnt++;
        r = lca(r, v);
        seen[v] = 1;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> k;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    prep();

    for (int i = 1; i <= n; i++) {
        cin >> c[i];

        l[c[i]] = lca(l[c[i]], i);
    }

    for (int i = 1; i <= n; i++)
        cum[i]++, cum[l[c[i]]]--;

    run();

    dfs();

    if (!r) {
        cout << 0 << '\n';
        return 0;
    }

    int need = 0;
    while (r != 1) {
        if (!cum[r])
            need = 1;

        r = lift[r][0];
    }

    cout << cnt + need - 1 << '\n';

    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 29756 KB Output is correct
2 Incorrect 36 ms 30548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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