Submission #956087

#	Time	Username	Problem	Language	Result	Execution time	Memory
956087		Pring	Mergers (JOI19_mergers)	C++17	100 / 100	749 ms	135352 KiB

mergers

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 500005;
int n, m, clr[MXN];
vector<int> sclr[MXN];

struct BIT {
    int n, val[MXN];
    void init(int _n) {
        n = _n;
        fill(val + 1, val + n + 1, 0);
    }
    void modify(int id, int v) {
        for (; id <= n; id += (id & -id)) val[id] += v;
    }
    void modify(int l, int r, int v) {
        modify(l, v);
        modify(r, -v);
    }
    int query(int id) {
        int ans = 0;
        for (; id > 0; id -= (id & -id)) ans += val[id];
        return ans;
    }
} B;

struct DSU {
    int p[MXN];
    void init(int n) {
        fill(p + 1, p + n + 1, -1);
    }
    int find(int x) {
        return (p[x] < 0 ? x : p[x] = find(p[x]));
    }
    bool onion(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (p[x] > p[y]) swap(x, y);
        p[x] += p[y];
        p[y] = x;
        return true;
    }
} dsu;

namespace TREE {
    vector<int> edge[MXN];
    int p[MXN], d[MXN], sz[MXN], son[MXN], top[MXN], dfn[MXN], C;
    int idfn[MXN];
    int deg[MXN];

    void PUSH_EDGE(int x, int y) {
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    void DFS(int id, int par, int dep) {
        p[id] = par;
        d[id] = dep;
        sz[id] = 1;
        son[id] = -1;
        for (auto &i : edge[id]) {
            if (i == par) continue;
            DFS(i, id, dep + 1);
            sz[id] += sz[i];
            if (son[id] == -1) son[id] = i;
            else if (sz[son[id]] < sz[i]) son[id] = i;
        }
    }

    void HLD(int id, int par, int _t) {
        top[id] = _t;
        dfn[id] = C++;
        if (son[id] != -1) HLD(son[id], id, _t);
        for (auto &i : edge[id]) {
            if (i == par) continue;
            if (i == son[id]) continue;
            HLD(i, id, i);
        }
    }

    void BUILD() {
        DFS(1, 0, 0);
        C = 1;
        HLD(1, 0, 1);
        FOR(i, 1, n) idfn[dfn[i]] = i;
        B.init(n);
    }

    int LCA(int x, int y) {
        while (top[x] != top[y]) {
            if (d[top[x]] < d[top[y]]) swap(x, y);
            B.modify(dfn[top[x]], dfn[x] + 1, 1);
            x = p[top[x]];
        }
        if (d[x] < d[y]) swap(x, y);
        B.modify(dfn[y] + 1, dfn[x] + 1, 1);
        return y;
    }

    void COLOR(vector<int> &v) {
        int lca = v[0];
        FOR(i, 1, v.size()) {
            lca = LCA(lca, v[i]);
        }
    }

    void MERGE() {
        vector<int> v;
        dsu.init(n);
        FOR(i, 2, n + 1) {
            if (B.query(dfn[i])) {
                debug(i, p[i], 1);
                dsu.onion(i, p[i]);
            } else {
                v.push_back(i);
            }
        }
        for (auto &i : v) {
            debug(i, p[i], 0);
            deg[dsu.find(i)]++;
            deg[dsu.find(p[i])]++;
        }
    }

    int LEAF() {
        int ans = 0;
        FOR(i, 1, n + 1) {
            if (dsu.p[i] >= 0) continue;
            if (deg[i] <= 1) ans++;
        }
        return ans;
    }
}

int miku() {
    int x, y;
    cin >> n >> m;
    FOR(i, 1, n) {
        cin >> x >> y;
        TREE::PUSH_EDGE(x, y);
    }
    TREE::BUILD();
    FOR(i, 1, n + 1) {
        cin >> clr[i];
        sclr[clr[i]].push_back(i);
    }
    FOR(i, 1, m + 1) TREE::COLOR(sclr[i]);
    TREE::MERGE();
    x = TREE::LEAF();
    if (x == 1) return 0;
    return (x - 1) / 2 + 1;
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    cout << miku() << '\n';
    return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'void TREE::MERGE()':
mergers.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
mergers.cpp:131:17: note: in expansion of macro 'debug'
  131 |                 debug(i, p[i], 1);
      |                 ^~~~~
mergers.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
mergers.cpp:138:13: note: in expansion of macro 'debug'
  138 |             debug(i, p[i], 0);
      |             ^~~~~

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