제출 #1124858

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124858		denislav	수도 (JOI20_capital_city)	C++20	0 / 100	3094 ms	26512 KiB

capital_city

# include <iostream>
# include <algorithm>
# include <queue>
# include <vector>
# include <cassert>
# include <cmath>
using namespace std;

const int MAX=2e5+11;

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

int parrent[MAX];
bool vis[MAX];
bool vis_col[MAX];

void dfs(int curr, int par)
{
    parrent[curr]=par;
    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;
        dfs(nxt,curr);
    }
}

void init()
{
    for(int i=1;i<=n;i++)
    {
        vis[i]=0;
        vis_col[i]=0;
        parrent[i]=0;
    }
}

int solve(int color)
{
    init();
    int top=c[color][0];
    dfs(top,0);

    queue<int> q;
    vis[top]=1;
    vis_col[color]=1;
    for(int x: c[color]) q.push(x);

    int ans=0;
    while(q.size()>0)
    {
        int curr=q.front();
        q.pop();

        while(!vis[curr])
        {
            vis[curr]=1;
            if(!vis_col[col[curr]])
            {
                ans++;
                vis_col[col[curr]]=1;
                for(int x: c[col[curr]]) q.push(x);
            }

            curr=parrent[curr];
        }
    }

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>col[i];
        c[col[i]].push_back(i);
    }

    int ans=1e9;
    for(int i=1;i<=k;i++) ans=min(ans,solve(i));

    if(ans>=(int)sqrt(n)+2) assert(0);
    cout<<ans<<"\n";

    return 0;
}

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