Submission #1164389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164389		antonn	Mergers (JOI19_mergers)	C++20	0 / 100	54 ms	48316 KiB

mergers

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 5e5 + 7;

vector<int> g[N];
int c[N], f[N], cnt[N];
map<int, int> s[N];
int l[N], r[N], tt = 0, who[N], par[N], seen[N], bad[N], taken[N], down[N];

void dfs(int u, int p = 0) {
    par[u] = p;
    l[u] = ++tt;
    who[tt] = u;
    for (auto v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
        
        if (s[v].size() > s[u].size()) swap(s[u], s[v]), swap(cnt[u], cnt[v]);
        for (auto it : s[v]) {
            s[u][it.F] += it.S;
            if (s[u][it.F] == f[it.F]) ++cnt[u];
        }
    }
    s[u][c[u]] += 1; if (s[u][c[u]] == f[c[u]]) ++cnt[u];
    if (u != 1 && cnt[u] == s[u].size()) bad[u] = 1;
    r[u] = tt;
}

void calc_down(int u, int p = 0) {
    down[u] = bad[u];
    for (auto v : g[u]) {
        if (v != p) {
            calc_down(v, u);
            down[u] += down[v];
        }
    }
}

pi t[4 * N];
int lazy[4 * N];

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = {0, tl};
        return;
    }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}

void push(int v, int tl, int tr) {
    if (tl < tr) {
        lazy[2 * v] += lazy[v];
        lazy[2 * v + 1] += lazy[v];
    }
    t[v].F += lazy[v];
    lazy[v] = 0;
}

void add(int v, int tl, int tr, int l, int r, int x) {
    push(v, tl, tr);
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
        lazy[v] += x;
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    add(2 * v, tl, tm, l, r, x);
    add(2 * v + 1, tm + 1, tr, l, r, x);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}

int main() {
    ios::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].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 1; i <= n; ++i) ++f[c[i]];
    
    dfs(1);
    build(1, 1, n);
    int total_bad = 0;
    for (int i = 1; i <= n; ++i) if (bad[i]) add(1, 1, n, l[i], r[i], +1), ++total_bad;
    
    calc_down(1);
    int ans = 0;
    for (auto x : g[1]) if (down[x] == total_bad) ++ans;
    while (true) {
        push(1, 1, n);
        pi x = t[1];
        if (x.F == 0) break;
        
        int u = who[x.S];
        ++ans;
        while (u != 0 && !seen[u]) {
            if (bad[u] == 1) {
                bad[u] = 0;
                add(1, 1, n, l[u], r[u], -1);
            }
            seen[u] = 1;
            u = par[u];
        }
    }
    cout << (ans + 1) / 2 << "\n";
}

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