oj.uz

답안 #1083472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1083472 2024-09-03T09:09:56 Z Sharky Mergers (JOI19_mergers) C++17
0 / 100
 95 ms 74440 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];
set<int> g[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);
            }
        }
    }
    for (int u = 1; u <= n; u++) for (int &v : adj[u]) if (find(u) != find(v)) g[find(u)].insert(find(v));
    for (int i = 1; i <= n; i++) if ((int) g[i].size() == 1) leaf++;
    cout << leaf / 2 << '\n';
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 47452 KB Output is correct
2 Correct 23 ms 47452 KB Output is correct
3 Correct 18 ms 47448 KB Output is correct
4 Correct 19 ms 47416 KB Output is correct
5 Correct 21 ms 47372 KB Output is correct
6 Correct 20 ms 47452 KB Output is correct
7 Correct 21 ms 47396 KB Output is correct
8 Correct 19 ms 47452 KB Output is correct
9 Correct 18 ms 47468 KB Output is correct
10 Correct 21 ms 47452 KB Output is correct
11 Correct 21 ms 47444 KB Output is correct
12 Correct 21 ms 47448 KB Output is correct
13 Correct 22 ms 47312 KB Output is correct
14 Incorrect 20 ms 47440 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 47452 KB Output is correct
2 Correct 23 ms 47452 KB Output is correct
3 Correct 18 ms 47448 KB Output is correct
4 Correct 19 ms 47416 KB Output is correct
5 Correct 21 ms 47372 KB Output is correct
6 Correct 20 ms 47452 KB Output is correct
7 Correct 21 ms 47396 KB Output is correct
8 Correct 19 ms 47452 KB Output is correct
9 Correct 18 ms 47468 KB Output is correct
10 Correct 21 ms 47452 KB Output is correct
11 Correct 21 ms 47444 KB Output is correct
12 Correct 21 ms 47448 KB Output is correct
13 Correct 22 ms 47312 KB Output is correct
14 Incorrect 20 ms 47440 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 47452 KB Output is correct
2 Correct 23 ms 47452 KB Output is correct
3 Correct 18 ms 47448 KB Output is correct
4 Correct 19 ms 47416 KB Output is correct
5 Correct 21 ms 47372 KB Output is correct
6 Correct 20 ms 47452 KB Output is correct
7 Correct 21 ms 47396 KB Output is correct
8 Correct 19 ms 47452 KB Output is correct
9 Correct 18 ms 47468 KB Output is correct
10 Correct 21 ms 47452 KB Output is correct
11 Correct 21 ms 47444 KB Output is correct
12 Correct 21 ms 47448 KB Output is correct
13 Correct 22 ms 47312 KB Output is correct
14 Incorrect 20 ms 47440 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 62184 KB Output is correct
2 Incorrect 95 ms 74440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 47452 KB Output is correct
2 Correct 23 ms 47452 KB Output is correct
3 Correct 18 ms 47448 KB Output is correct
4 Correct 19 ms 47416 KB Output is correct
5 Correct 21 ms 47372 KB Output is correct
6 Correct 20 ms 47452 KB Output is correct
7 Correct 21 ms 47396 KB Output is correct
8 Correct 19 ms 47452 KB Output is correct
9 Correct 18 ms 47468 KB Output is correct
10 Correct 21 ms 47452 KB Output is correct
11 Correct 21 ms 47444 KB Output is correct
12 Correct 21 ms 47448 KB Output is correct
13 Correct 22 ms 47312 KB Output is correct
14 Incorrect 20 ms 47440 KB Output isn't correct
15 Halted 0 ms 0 KB -