Submission #824219

#	Time	Username	Problem	Language	Result	Execution time	Memory
824219		vjudge1	Mergers (JOI19_mergers)	C++17	100 / 100	900 ms	233108 KiB

mergers

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

static const int N = 1e6 + 10;
class lca_t {
       public:
        int rmq[20][N];
        int pos[N], d[N];
        vector<int> adj[N];
        int timer;
        int n;

        lca_t(int n = 0) : n(n) {}

        void add_edge(int u, int v) {
                adj[u].emplace_back(v);
                adj[v].emplace_back(u);
        }

        void dfs(int u, int p) {
                rmq[0][timer++] = u;
                for (int v : adj[u]) {
                        if (v == p) continue;
                        d[v] = d[u] + 1;
                        dfs(v, u);
                        rmq[0][timer++] = u;
                }
        }

        void build(int root) {
                timer = 0;
                d[root] = 0;
                dfs(root, -1);
                for (int i = 0; i < timer; i++) pos[rmq[0][i]] = i;
                assert(__lg(timer) < 20);
                for (int i = 1; i <= __lg(timer); i++) {
                        for (int j = 0; j + (1 << i) <= timer; j++) {
                                rmq[i][j] = d[rmq[i - 1][j]] < d[rmq[i - 1][j + (1 << (i - 1))]]
                                                ? rmq[i - 1][j]
                                                : rmq[i - 1][j + (1 << (i - 1))];
                        }
                }
        }

        int get(int u, int v) {
                int l = pos[u], r = pos[v];
                if (l > r) swap(l, r);
                int i = __lg(r - l + 1);
                r -= (1 << i) - 1;
                return d[rmq[i][l]] < d[rmq[i][r]] ? rmq[i][l] : rmq[i][r];
        }

} lca;

class DSU {
       public:
        DSU(int n) {
                prt.resize(n + 1, -1);
        }

        int SZ(int u) {
                return -prt[root(u)];
        }

        int root(int u) {
                return (prt[u] < 0 ? u : (prt[u] = root(prt[u])));
        }

        bool connected(int u, int v) {
                return ((u = root(u)) == (v = root(v)));
        }

        bool unite(int u, int v) {
                if ((u = root(u)) == (v = root(v))) {
                        return 0;
                }

                if (prt[u] > prt[v]) {
                        u ^= v ^= u ^= v;
                }

                prt[u] += prt[v];
                prt[v] = u;
                return 1;
        }

       private:
        vector<int> prt;
};

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, k;
        cin >> n >> k;
        vector<vector<int>> adj(n);
        for (int i = 0; i < n - 1; i++) {
                int u, v;
                cin >> u >> v;
                u--, v--;
                adj[u].emplace_back(v);
                adj[v].emplace_back(u);
                lca.add_edge(u, v);
        }
        vector<vector<int>> group(k);
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i], a[i]--;
        for (int i = 0; i < n; i++) group[a[i]].emplace_back(i);
        lca.build(0);
        vector<int> pf(n, 0);
        for (int i = 0; i < k; i++) {
                int top = group[i][0];
                for (int j : group[i]) top = lca.get(top, j);
                pf[top] -= group[i].size();
                for (int j : group[i]) pf[j]++;
        }
        DSU dsu(n);
        function<void(int, int)> dfs = [&](int u, int p) {
                for (int v : adj[u]) {
                        if (v == p) continue;
                        dfs(v, u);
                        pf[u] += pf[v];
                        if (pf[v]) {
                                dsu.unite(u, v);
                        }
                }
        };
        dfs(0, -1);
        vector<int> deg(n);
        for (int i = 0; i < n; i++) {
                for (int j : adj[i]) {
                        if (i > j) continue;
                        int x = dsu.root(i), y = dsu.root(j);
                        if (x == y) continue;
                        deg[x]++, deg[y]++;
                }
        }
        int res = 0;
        for (int i = 0; i < n; i++) res += deg[i] == 1;
        cout << (res + 1 >> 1);
}

Compilation message (stderr)

mergers.cpp: In function 'int32_t main()':
mergers.cpp:141:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  141 |         cout << (res + 1 >> 1);
      |                  ~~~~^~~

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