Submission #699456

#	Time	Username	Problem	Language	Result	Execution time	Memory
699456		nguyentunglam	Mergers (JOI19_mergers)	C++17	100 / 100	945 ms	170012 KiB

mergers

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 5e5 + 10;
int c[21][N * 2], st[N], lab[N], f[N], g[N];
vector<int> adj[N], lst[N];
int cnt;
void dfs(int u) {
    c[0][++cnt] = u;
    st[u] = cnt;
    for(int &v : adj[u]) if (!st[v]) {
        dfs(v);
        c[0][++cnt] = u;
    }
}
int lca(int u, int v) {
    int l = st[u], r = st[v];
    if (l > r) swap(l, r);
    int k = log2(r - l + 1);
    int x = c[k][l], y = c[k][r - (1 << k) + 1];
    return st[x] < st[y] ? x : y;
}
int root(int v) {
    return lab[v] < 0 ? v : lab[v] = root(lab[v]);
}
void join(int u, int v) {
    u = root(u); v = root(v);
    if (u == v) return;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
}
void scan(int u, int par) {
    for(int &v : adj[u]) if (v != par) {
        scan(v, u);
        f[u] += f[v];
    }
    if (f[u] && par) join(u, par);
}
int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int n, k; cin >> n >> k;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    for(int j = 1; j <= log2(cnt); j++) for(int i = 1; i <= cnt; i++) {
        int x = c[j - 1][i], y = c[j - 1][i + (1 << (j - 1))];
        c[j][i] = st[x] < st[y] ? x : y;
    }
    for(int i = 1; i <= n; i++) {
        int s; cin >> s;
        lst[s].push_back(i);
        lab[i] = -1;
    }
    for(int color = 1; color <= k; color++) if (!lst[color].empty()) {
        int p = lst[color].back();
        for(int &j : lst[color]) p = lca(p, j);
        for(int &j : lst[color]) {
            f[j]++; f[p]--;
        }
    }
    scan(1, 0);
    for(int u = 1; u <= n; u++) {
        for(int &v : adj[u]) if (root(v) != root(u)) {
            g[root(u)]++, g[root(v)]++;
        }
    }
    int leaf = 0;
    for(int i = 1; i <= n; i++) if (g[i] == 2) leaf++;
    cout << (leaf + 1) / 2;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:47:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mergers.cpp:48:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mergers.cpp:51:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mergers.cpp:52:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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