Submission #993161

#	Time	Username	Problem	Language	Result	Execution time	Memory
993161		prvocislo	Capital City (JOI20_capital_city)	C++17	11 / 100	2498 ms	524288 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;

struct scc
{
    int n;
    vector<vector<int>> adj, adj_rev;
    vector<bool> used, in;
    vector<int> order, component, cnt;
    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)
    {
        //cout << u << " " << v << "\n";
        adj[u].push_back(v);
        adj_rev[v].push_back(u);
    }
    void init(int m)
    {
        adj.assign(m, {}), adj_rev.assign(m, {}), used.assign(m, false), in.assign(m, false), cnt.assign(m, 0), order.clear(), component.clear();
        n = m;
    }
    int solve() 
    {
        used.assign(n, false);
        for (int i = 0; i < n; i++)
            if (!used[i])
                dfs1(i);
        used.assign(n, false);
        reverse(order.begin(), order.end());
        int ans = n;
        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;
    }
};

const int logn = 20;
//const int logn = 4;
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 n, k;
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);
    scc s;
    s.init(k + logn * n);
    for (int i = 0; i < n; i++)
    {
        s.add(k + i, c[i]);
        for (int b = 1; b < logn; b++) s.add(k + n * b + i, k + n * (b - 1) + i), s.add(k + n * b + i, k + n * (b - 1) + l[b - 1][i]);
    }
    for (int i = 0; i < k; i++)
    {
        s.cnt[i] = 1;
        int lc = col[i][0];
        for (int j : col[i]) lc = lca(lc, j);
        s.add(i, k + lc);
        for (int j : col[i])
        {
            for (int b = logn - 1; b >= 0; b--) if (d[l[b][j]] >= d[lc])
                s.add(i, k + b * n + j), j = l[b][j];
        }
    }
    cout << s.solve() << "\n";
    return 0;
}

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