제출 #1241725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241725		CrabCNH	Mergers (JOI19_mergers)	C++20	0 / 100	20 ms	19388 KiB

mergers

#include <bits/stdc++.h>

#define pii pair <int, int>
#define fi first
#define se second

using namespace std;

const int maxN = 5e5 + 1;

int S[maxN], par[maxN], sz[maxN];
vector <int> adj[maxN];
int last[maxN];
int cnt[maxN];
int up[maxN], depth[maxN];

const int BUFFER_SIZE = 1 << 20;
char input_buffer[BUFFER_SIZE];
int input_pos = 0, input_len = 0;

inline char nextChar() {
    if (input_pos == input_len) {
        input_pos = 0;
        input_len = fread(input_buffer, 1, BUFFER_SIZE, stdin);
        if (input_len == 0) return EOF;
    }
    return input_buffer[input_pos++];
}

inline void fast_read(int &x) {
    x = 0;
    char c;
    bool neg = false;
    do {
        c = nextChar();
    } while (c != '-' && (c < '0' || c > '9'));

    if (c == '-') {
        neg = true;
        c = nextChar();
    }

    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = nextChar();
    }

    if (neg) x = -x;
}

inline void init (int n) {
    for (int i = 1; i <= n; i ++) {
        par[i] = i;
        sz[i] = 1;
    }
}

int getRoot (int u) {
    if (par[u] == u) {
        return u;
    }
    return (par[u] = getRoot (par[u]));
}

inline void join (int u, int v) {
    u = getRoot (u);
    v = getRoot (v);
    if (u == v) {
        return;
    }
    if (sz[u] < sz[v]) {
        swap (u, v);
    }
    par[v] = u;
    sz[u] += sz[v];
    return;
}

inline void merge (int u, int v) {
    while (u != v) {
        //cout << u << ' ' << v << '\n';
        if (depth[u] > depth[v]) {
            swap (u, v);
        }
        join (v, up[v]);
        v = up[v];
    }
}

void dfs (int u, int p) {
    up[u] = p;
    for (auto v : adj[u]) {
        if (v == p) {
            continue;
        }
        depth[v] = depth[u] + 1;
        dfs (v, u);
    }
}

int main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    int n, k;
    fast_read (n);
    fast_read (k);
    init (n);
    for (int i = 1; i < n; i ++) {
        int u, v;
        fast_read (u);
        fast_read (v);
        adj[u].push_back (v);
        adj[v].push_back (u);
    }
    dfs (1, 0);
    for (int i = 1; i <= n; i ++) {
        fast_read (S[i]);
        if (last[S[i]] != 0) {
            merge (i, last[S[i]]);
        }
        last[S[i]] = i;
    }
    int res = 0;
    for (int u = 1; u <= n; u ++) {
        for (auto v : adj[u]) {
            int i = getRoot (u);
            int j = getRoot (v);
            if (i != j) {
                cnt[i] ++;
            }
        }
        res += (cnt[u] == 1);
    }
    cout << (res + 1) / 2;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30