Submission #993171

#	Time	Username	Problem	Language	Result	Execution time	Memory
993171		prvocislo	Capital City (JOI20_capital_city)	C++17	11 / 100	3074 ms	506016 KiB

capital_city

// meow cat, please meow back =^_^=

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

int n, k;
const int logn = 18;
const int maxn = 200005 * (logn + 1);
int m;
vector<int> adj[maxn], adj_rev[maxn];
bool used[maxn], in[maxn];
int cnt[maxn];
vector<int> order, component;
void dfs1(int v) {
    used[v] = true;

    for (auto u : adj[v])
        if (!used[u])
            dfs1(u);

    order.push_back(v);
}

void dfs2(int v) {
    used[v] = true;
    component.push_back(v);

    for (auto u : adj_rev[v])
        if (!used[u])
            dfs2(u);
}
void add(int u, int v)
{
    adj[u].push_back(v);
    adj_rev[v].push_back(u);
}
int solve()
{
    fill(used, used + m, false);
    for (int i = 0; i < m; i++)
        if (!used[i])
            dfs1(i);
    fill(used, used + m, false);
    reverse(order.begin(), order.end());
    int ans = m;
    for (auto v : order)
        if (!used[v]) {
            dfs2(v);
            bool okay = true; int c = 0;
            for (int i : component) in[i] = true;
            for (int i : component)
            {
                if (cnt[i]) c++;
                for (int j : adj[i]) if (!in[j]) okay = false;
            }
            for (int i : component) in[i] = false;
            if (c && okay)
                ans = min(ans, c - 1);
            component.clear();
        }
    return ans;
}

vector<vector<int> > g, l, col;
vector<int> d, c;
void dfs(int u)
{
    for (int j = 1; j < logn; j++) l[j][u] = l[j - 1][l[j - 1][u]];
    for (int v : g[u]) if (v != l[0][u]) d[v] = d[u] + 1, l[0][v] = u, dfs(v);
}
int lca(int u, int v)
{
    if (d[u] < d[v]) swap(u, v);
    for (int i = logn - 1; i >= 0; i--) if (d[l[i][u]] >= d[v]) u = l[i][u];
    for (int i = logn - 1; i >= 0; i--) if (l[i][u] != l[i][v]) u = l[i][u], v = l[i][v];
    return u == v ? u : l[0][u];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    g.assign(n, {}), l.assign(logn, vector<int>(n, 0)), d.assign(n, 0), col.assign(k, {}), c.assign(n, -1);
    for (int i = 0, a, b; i < n - 1; i++) cin >> a >> b, g[--a].push_back(--b), g[b].push_back(a);
    for (int i = 0; i < n; i++)
    {
        cin >> c[i];
        col[--c[i]].push_back(i);
    }
    dfs(0);
    m = k + logn * n;
    for (int i = 0; i < n; i++)
    {
        add(k + i, c[i]);
        for (int b = 1; b < logn; b++) add(k + n * b + i, k + n * (b - 1) + i), add(k + n * b + i, k + n * (b - 1) + l[b - 1][i]);
    }
    for (int i = 0; i < k; i++)
    {
        cnt[i] = 1;
        int lc = col[i][0];
        for (int j : col[i]) lc = lca(lc, j);
        add(i, k + lc);
        for (int j : col[i])
        {
            for (int b = logn - 1; b >= 0; b--) if (d[l[b][j]] >= d[lc])
                add(i, k + b * n + j), j = l[b][j];
        }
    }
    cout << solve() << "\n";
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59