Submission #376724

#	Time	Username	Problem	Language	Result	Execution time	Memory
376724		2qbingxuan	Mergers (JOI19_mergers)	C++14	0 / 100	69 ms	20584 KiB

mergers

#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : "\033[0m)\n")));
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;
const int64_t INF = 1e18;
const int maxn = 500025;

struct Dsu {
    int pa[maxn], rk[maxn];
    int anc(int x) { return x==pa[x] ? x : pa[x] = anc(pa[x]); }
    void init(int n) {
        for (int i = 1; i <= n; i++)
            pa[i] = i, rk[i] = 0;
    }
    bool join(int x, int y) {
        if ((x=anc(x)) == (y=anc(y))) return false;
        if (rk[x] < rk[y]) swap(x, y);
        return pa[y] = x, rk[x]!=rk[y] || ++rk[x];
    }
} dsu;

vector<int> g[maxn];
vector<pair<int,int>> ed;
int s[maxn];
int cnt[2][maxn], has;
void dfs(int i, int p = 0) {
    if (has > 0) {
        dsu.join(i, p);
    } else if (p) {
        ed.emplace_back(i, p);
    }
    has -= (min(cnt[0][s[i]], cnt[1][s[i]]) > 0);
    cnt[0][s[i]] -= 1;
    cnt[1][s[i]] += 1;
    has += (min(cnt[0][s[i]], cnt[1][s[i]]) > 0);
    for (int j: g[i]) {
        if (j != p) {
            dfs(j, i);
        }
    }
    has -= (min(cnt[0][s[i]], cnt[1][s[i]]) > 0);
    cnt[0][s[i]] += 1;
    cnt[1][s[i]] -= 1;
    has += (min(cnt[0][s[i]], cnt[1][s[i]]) > 0);
}
bool vis[maxn];
int leaf = 0;
void dfs2(int i) {
    debug(i);
    if (g[i].size() == 1) ++leaf;
    vis[i] = true;
    for (int j: g[i]) {
        if (!vis[j])
            dfs2(j);
    }
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) ++cnt[0][s[i]];
    dsu.init(n);
    dfs(1);
    for (int i = 1; i <= n; i++) g[i].clear();
    for (auto [a, b]: ed) {
        a = dsu.anc(a);
        b = dsu.anc(b);
        g[a].emplace_back(b);
        g[b].emplace_back(a);
        debug(a, b);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) if (!vis[i]) {
        leaf = 0;
        dfs2(i);
        debug(leaf);
        ans += (leaf + 1) / 2;
    }
    cout << ans << '\n';
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:83:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     for (auto [a, b]: ed) {
      |               ^

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