Submission #1116879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116879		vjudge1	Mergers (JOI19_mergers)	C++17	48 / 100	3065 ms	79472 KiB

mergers

#include <bits/stdc++.h>
#define int long long
#define double long double
#define arr2 array<int, 2>
#define popcount __builtin_popcountll
#define ctz __builtin_ctzll
#define arr3 array<int, 3>

using namespace std;

const int N = 5e5 + 10, M = 1e9 + 7;

vector<int> adj[N];
int n, k;
int col[N];
int cnt[N];
int ths[N];
int par[N];
int sz[N];
int cnt1[N];
vector<arr2> cut;
stack<vector<int>> stk;

void crt(int a) {
    par[a] = a;
    sz[a] = 1;
}

int get(int a) {
    return (a == par[a] ? a : (par[a] = get(par[a])));
}

void mrg(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) {
        return;
    }
    if (sz[a] > sz[b]) {
        swap(a, b);
    }
    par[a] = b;
    sz[b] = sz[a] + sz[b];
}

bool same(int a, int b) {
    return get(a) == get(b);
}

void dfs(int a, int b = 0) {
    stk.push(vector<int>(k + 1));
    for (int i = 0; i <= k; ++i) {
        stk.top()[i] = ths[i];
    }
    ths[col[a]]++;
    for (int i : adj[a]) {
        if (i != b) {
            dfs(i, a);
        }
    }
    if (a == 1) {
        return;
    }
    for (int i = 0; i <= k; ++i) {
        if ((ths[i] - stk.top()[i] != 0) and (ths[i] - stk.top()[i] != cnt[i])) {
            mrg(a, b);
            stk.pop();
            return;
        }
    }
    cut.push_back({a, b});
    stk.pop();
}

void fun() {
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i) {
        int a;
        cin >> a;
        col[i] = a;
        cnt[a]++;
        crt(i);
    }
    dfs(1);
    for (arr2 i : cut) {
        cnt1[get(i[0])]++, cnt1[get(i[1])]++;
    }
    int c = 0;
    for (int i = 1; i <= n; ++i) {
        if (cnt1[i] == 1) {
            c++;
        }
    }
    cout << (c + 1) / 2 << "\n";
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // int tc;
    // cin >> tc;
    // while (tc--)
    fun();
}

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