Submission #899039

#	Time	Username	Problem	Language	Result	Execution time	Memory
899039		danikoynov	Capital City (JOI20_capital_city)	C++14	0 / 100	275 ms	39596 KiB

capital_city

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;

int n, k, c[maxn];
vector < int > adj[maxn];
vector < int > col[maxn];

void input()
{
    cin >> n >> k;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
        ///cout << "edge " << v << " " << u << endl;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    for (int i = 1; i <= n; i ++)
        cin >> c[i], col[c[i]].push_back(i);
}


int sub[maxn], par[maxn], last[maxn], used[maxn];
int timer;
void calc(int v, int p)
{
    //cout << "calc " << v << " " << p << endl;
    last[v] = timer;
    par[v] = p;
    sub[v] = 1;
    for (int u : adj[v])
    {
        //cout << "neib " << v << " " << u << endl;
        if (used[u] || u == p)
            continue;

        calc(u, v);
        sub[v] += sub[u];
    }
}

int find_centroid(int v, int p, int sz)
{
    for (int u : adj[v])
    {
        if (u == p || used[u])
            continue;
        if (sub[u] >= sz / 2)
            return find_centroid(u, v, sz);
    }

    return v;
}

int ans, mark[maxn];

void make_tree(int v)
{
    /**cout << "make tree" << endl;
    for (int i = 1; i <= n; i ++)
        cout << last[i] << " ";
    cout << endl;*/
    vector < int > cs;
    /**for (int i = 1; i <= k; i ++)
        mark[i] = 0;*/

    queue < int > q;

    for (int cur : col[c[v]])
    {
        if (last[cur] != timer)
            return;
        q.push(cur);
    }

    mark[c[v]] = 1;
    cs.push_back(c[v]);
    int cnt = 0;
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        ///cout << "queue " << cur << endl;
        if (par[cur] != -1 && !mark[c[par[cur]]])
        {
            cnt ++;
            mark[c[par[cur]]] = 1;
            cs.push_back(c[par[cur]]);
            for (int ver : col[c[par[cur]]])
            {
                if (last[ver] != timer)
                {
                    for (int ps : cs)
                        mark[ps] = 0;
                    return;
                }
                q.push(ver);
            }
        }
    }
    ///cout << cnt << endl;
    ans = min(ans, cnt);
    for (int ps : cs)
        mark[ps] = 0;
    ///exit(0);
}

void decompose(int v)
{
    timer ++;
    calc(v, -1);
    int centroid = find_centroid(v, -1, sub[v]);
    ///cout << "centroid " << v << endl;
    make_tree(centroid);
    used[centroid] = 1;
    for (int u : adj[centroid])
    {
        if (!used[u])
            decompose(u);
    }
}
void solve()
{
    input();
    ans = n;
    decompose(1);
    cout << ans << endl;
}

int main()
{
    speed();
    solve();
    return 0;
}

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