제출 #1155465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155465		ivaziva	Capital City (JOI20_capital_city)	C++20	0 / 100	468 ms	33188 KiB

capital_city

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200001

int n,k;
vector<int> adj[MAXN];
int c[MAXN],promenjeno[MAXN],siz[MAXN];
bool uklonjeno[MAXN];
map<int,int> mapa;
int ans=0,boja;

void subtree_size(int node,int pret)
{
    siz[node]=1;
    for (int sled:adj[node])
    {
        if (sled==pret or uklonjeno[sled]) continue;
        subtree_size(sled,node);siz[node]+=siz[sled];
    }
}

int get_centroid(int node,int pret,int val)
{
    for (int sled:adj[node])
    {
        if (sled==pret or uklonjeno[sled]) continue;
        if (siz[sled]*2>val) return get_centroid(sled,node,val);
    }
    return node;
}

void racunaj(int node,int pret,int maxvalue,int bojaa)
{
    if (mapa.find(promenjeno[c[node]])==mapa.end() and promenjeno[c[node]]!=bojaa) mapa[promenjeno[c[node]]]=1;
    else if (mapa[promenjeno[c[node]]]<maxvalue and promenjeno[c[node]]!=bojaa) {mapa[promenjeno[c[node]]]++;boja=min(boja,promenjeno[c[node]]);}
    for (int sled:adj[node])
    {
        if (sled==pret or uklonjeno[sled]) continue;
        racunaj(sled,node,maxvalue,bojaa);
    }
}

void centroid_decomposition(int node)
{
    subtree_size(node,-1);
    int centroida=get_centroid(node,-1,siz[node]);uklonjeno[centroida]=true;
    boja=INT_MAX;int broj=1;
    for (int sled:adj[centroida])
    {
        if (uklonjeno[sled]) continue;
        racunaj(sled,centroida,broj,promenjeno[c[centroida]]);broj++;if (boja!=INT_MAX) break;
    }
    mapa.clear();
    if (boja!=INT_MAX) {promenjeno[c[centroida]]=boja;ans++;}
    for (int sled:adj[node])
    {
        if (!uklonjeno[sled]) centroid_decomposition(sled);
    }
}

int main()
{
    cin>>n>>k;
    for (int i=1;i<n;i++) {int x,y;cin>>x>>y;adj[x].push_back(y);adj[y].push_back(x);}
    for (int i=1;i<=n;i++) cin>>c[i];
    for (int i=1;i<=k;i++) promenjeno[i]=i;
    centroid_decomposition(1);cout<<ans<<endl;
}

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