oj.uz

답안 #1083402

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1083402 2024-09-03T04:54:37 Z Sharky Mergers (JOI19_mergers) C++17
0 / 100
 80 ms 46280 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10, LG = 20;
int p[N], sz[N], dep[N], st[N][LG], conn[N], tin[N], timer = 0, cc = 0, leaf = 0;
vector<int> adj[N], sta[N];

int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    p[v] = u;
}

void dfs(int u, int p) {
    tin[u] = ++timer;
    for (int i = 1; i < LG; i++) {
        st[u][i] = st[st[u][i - 1]][i - 1];
    }
    for (int v : adj[u]) {
        if (v == p) continue;
        st[v][0] = u;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

int getLCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LG - 1; i >= 0; i--) {
        if ((dep[u] - dep[v]) & (1 << i)) {
            u = st[u][i];
        }
    }
    if (u == v) return u;
    for (int i = LG - 1; i >= 0; i--) {
        int ut = st[u][i], vt = st[v][i];
        if (ut != vt) u = ut, v = vt;
    }
    return st[u][0];
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    if (n == 1) {
        cout << "0\n";
        return 0;
    }
    for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    st[1][0] = 1;
    dfs(1, -1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sta[x].push_back(i);
    }
    for (int i = 1; i <= k; i++) {
        sort(sta[i].begin(), sta[i].end(), [&] (int x, int y) {
            return tin[x] < tin[y];
        });
        for (int j = 1; j < (int) sta[i].size(); j++) {
            int x = sta[i][j - 1], y = sta[i][j];
            int lca = getLCA(x, y);
            while (dep[x] > dep[lca]) {
                merge(st[x][0], x);
                x = find(x);
            }
            while (dep[y] > dep[lca]) {
                merge(st[y][0], y);
                y = find(y);
            }
        }
    }
    set<int> st;
    for (int i = 1; i <= n; i++) {
        if (adj[i].size() == 1) {
            st.insert(find(i));
        }
    }
    cout << (int) st.size() / 2 << '\n';
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 11 ms 23896 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 12 ms 23900 KB Output is correct
6 Correct 11 ms 23992 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23908 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 11 ms 23900 KB Output is correct
12 Incorrect 11 ms 23796 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 11 ms 23896 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 12 ms 23900 KB Output is correct
6 Correct 11 ms 23992 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23908 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 11 ms 23900 KB Output is correct
12 Incorrect 11 ms 23796 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 11 ms 23896 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 12 ms 23900 KB Output is correct
6 Correct 11 ms 23992 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23908 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 11 ms 23900 KB Output is correct
12 Incorrect 11 ms 23796 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 38716 KB Output is correct
2 Incorrect 80 ms 46280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 11 ms 23896 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 12 ms 23900 KB Output is correct
6 Correct 11 ms 23992 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23908 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 11 ms 23900 KB Output is correct
12 Incorrect 11 ms 23796 KB Output isn't correct
13 Halted 0 ms 0 KB -