제출 #1255674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255674		chikien2009	수도 (JOI20_capital_city)	C++20	100 / 100	492 ms	28520 KiB

capital_city

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, k, a, b, res = 1e9;
int c[200000], sz[200000], num[200000], pre[200000];
bool check[200000], vis[200000];
vector<int> g[200000], v[200000];

inline void PreCal(int node, int par)
{
    sz[node] = 1;
    vis[c[node]] = num[c[node]] = 0;
    for (auto &i : g[node])
    {
        if (i != par && !check[i])
        {
            PreCal(i, node);
            sz[node] += sz[i];
        }
    }
}

inline int Centroid(int node, int par, int lim)
{
    for (auto &i : g[node])
    {
        if (i != par && !check[i] && sz[i] * 2 > lim)
        {
            return Centroid(i, node, lim);
        }
    }
    return node;
}

inline void Get(int node, int par)
{
    num[c[node]]++;
    pre[node] = par;
    for (auto &i : g[node])
    {
        if (i != par && !check[i])
        {
            Get(i, node);
        }
    }
}

inline void DFS(int node)
{
    int val = 0, temp;
    vector<int> cur;
    PreCal(node, node);
    node = Centroid(node, node, sz[node]); // From now, the centroid is the variable node
    Get(node, node);                       // Spread out from the centroid
    check[node] = vis[c[node]] = true;
    cur.push_back(c[node]);
    while (!cur.empty())
    {
        temp = cur.back();
        cur.pop_back();
        if (num[temp] != v[temp].size())
        {
            val = 1e9;
            break;
        }
        val++;
        for (auto &i : v[temp])
        {
            if (!vis[c[pre[i]]])
            {
                vis[c[pre[i]]] = true;
                cur.push_back(c[pre[i]]);
            }
        }
    }
    res = min(res, val - 1);
    for (auto &i : g[node])
    {
        if (!check[i])
        {
            DFS(i);
        }
    }
}

int main()
{
    setup();

    cin >> n >> k;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> c[i];
        c[i]--;
        v[c[i]].push_back(i);
    }
    DFS(0);
    cout << res;
    return 0;
}

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