Submission #263172

#	Time	Username	Problem	Language	Result	Execution time	Memory
263172		keko37	Mergers (JOI19_mergers)	C++14	100 / 100	1273 ms	127928 KiB

mergers

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 500005;
const int LOG = 19;

int n, k, cnt;
int s[MAXN], par[MAXN][LOG], dub[MAXN], e[MAXN], ima[MAXN], bio[MAXN], deg[MAXN];
vector <int> v[MAXN], comp[MAXN];

void dfs (int x, int rod) {
    par[x][0] = rod;
    dub[x] = 1 + dub[rod];
    for (auto sus : v[x]) {
        if (sus == rod) continue;
        dfs(sus, x);
    }
}

void precompute () {
    dfs(1, 0);
    for (int i = 1; i < LOG; i++) {
        for (int j = 1; j <= n; j++) {
            par[j][i] = par[par[j][i - 1]][i - 1];
        }
    }
}

int digni (int x, int len) {
    int pot = 0;
    while (len > 0) {
        if (len & 1) x = par[x][pot];
        len /= 2;
        pot++;
    }
    return x;
}

int lca (int a, int b) {
    if (dub[a] < dub[b]) swap(a, b);
    a = digni(a, dub[a] - dub[b]);
    if (a == b) return a;
    for (int i = LOG - 1; i >= 0; i--) {
        if (par[a][i] != par[b][i]) {
            a = par[a][i];
            b = par[b][i];
        }
    }
    return par[a][0];
}

void obradi (int c) {
    int piv = comp[c][0];
    for (auto x : comp[c]) {
        if (x == piv) continue;
        int g = lca(piv, x);
        e[piv]++; e[x]++;
        e[g] -= 2;
    }
}

void nadi (int x, int rod) {
    for (auto sus : v[x]) {
        if (sus == rod) continue;
        nadi(sus, x);
        e[x] += e[sus];
    }
    if (rod != 0 && e[x] > 0) ima[x] = 1;
}

void oboji (int x) {
    if (bio[x]) return;
    bio[x] = cnt;
    for (auto sus : v[x]) {
        if (par[x][0] == sus && ima[x] || par[x][0] != sus && ima[sus]) oboji(sus);
    }
}

void build () {
    for (int i = 1; i <= n; i++) {
        if (bio[i] == 0) {
            cnt++;
            oboji(i);
        }
    }
}

int solve () {
    if (cnt == 1) return 0;
    for (int i = 2; i <= n; i++) {
        if (ima[i] == 0) {
            deg[bio[i]]++;
            deg[bio[par[i][0]]]++;
        }
    }
    int sol = 0;
    for (int i = 1; i <= cnt; i++) {
        if (deg[i] == 1) sol++;
    }
    return (sol + 1) / 2;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        comp[s[i]].push_back(i);
    }
    precompute();
    for (int i = 1; i <= k; i++) obradi(i);
    nadi(1, 0);
    build();
    cout << solve();
    return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'void oboji(int)':
mergers.cpp:76:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   76 |         if (par[x][0] == sus && ima[x] || par[x][0] != sus && ima[sus]) oboji(sus);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~

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