Submission #1014113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014113		alexdd	Capital City (JOI20_capital_city)	C++17	1 / 100	284 ms	34648 KiB

capital_city

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n,k,rez=INF;
vector<int> con[200005];
int color[200005];
int fr[200005];
int siz[200005];
bool iss[200005];
void get_sizes(int nod, int par)
{
    siz[nod]=1;
    for(auto adj:con[nod])
    {
        if(adj!=par && !iss[adj])
        {
            get_sizes(adj,nod);
            siz[nod]+=siz[adj];
        }
    }
}
int get_centroid(int nod, int par, int tot)
{
    for(auto adj:con[nod])
        if(adj!=par && !iss[adj] && 2*siz[adj]>tot)
            return get_centroid(adj,nod,tot);
    return nod;
}
int cnt_color[200005];
void get_cnt_color(int nod, int par, int mycolor)
{
    cnt_color[nod]=0;
    if(color[nod]==mycolor) cnt_color[nod]++;
    for(auto adj:con[nod])
    {
        if(adj!=par && !iss[adj])
        {
            get_cnt_color(adj,nod,mycolor);
            cnt_color[nod] += cnt_color[adj];
        }
    }
}
int auxrez=0;
map<int,int> mp;
void get_rez(int nod, int par)
{
    mp[color[nod]]++;
    for(auto adj:con[nod])
        if(adj!=par && !iss[adj] && cnt_color[adj]>0)
            get_rez(adj,nod);
}
void centroid_decomposition(int c)
{
    get_sizes(c,-1);
    c = get_centroid(c,-1,siz[c]);

    get_cnt_color(c,-1,color[c]);
    if(cnt_color[c]==fr[color[c]])
    {
        mp.clear();
        get_rez(c,-1);
        rez = min(rez, (int)mp.size()-1);
    }

    iss[c]=1;
    for(auto adj:con[c])
        if(!iss[adj])
            centroid_decomposition(adj);
}
signed main()
{
    cin>>n>>k;
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>color[i];
        fr[color[i]]++;
    }
    centroid_decomposition(1);
    cout<<rez;
    return 0;
}

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