Submission #218430

#	Time	Username	Problem	Language	Result	Execution time	Memory
218430		GioChkhaidze	Capital City (JOI20_capital_city)	C++14	100 / 100	876 ms	35056 KiB

capital_city

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int N=2e5+5;
int n,k,ans=1e9;
bool f[N],fix[N],lvl[N];
int c[N],P[N],Cf[N];
vector < int > v[N],s[N],h;

int Dfs(int x,int p,int sz,int &center) {
	int tot=1;
	Cf[c[x]]++;
	h.pb(x);
	for (int i=0; i<v[x].size(); i++) {
		int to=v[x][i];
		if (!lvl[to] && to!=p) 
			tot+=Dfs(to,x,sz,center); 
	}
	if (center==-1 && (2*tot>=sz || !p)) center=x;
	return tot;
}

void Go(int x,int p) {
	P[x]=p;
	for (int i=0; i<v[x].size(); i++) {
		int to=v[x][i];
		if (!lvl[to] && to!=p) Go(to,x);
	}
}

void Build(int x,int sz) {
	int center=-1;
	Dfs(x,0,sz,center);
	Go(center,0);
	queue < int > q;
	lvl[center]=1;
	q.push(center);
	int cn=0;
	while (!q.empty()) {
		int x=q.front();
		q.pop();
		if (fix[x]) continue;
		fix[x]=1;
		if (s[c[x]].size()!=Cf[c[x]]) {
			cn=1e9;
			while (!q.empty()) 
				q.pop();
			break;
		}
		if (!f[c[x]]) {
			cn++;
			f[c[x]]=1;
			for (int i=0; i<s[c[x]].size(); i++) 
				q.push(s[c[x]][i]);
		}
		if (P[x])
			q.push(P[x]);
	}

	for (int i=0; i<h.size(); i++) {
		int x=h[i];
		Cf[c[x]]=f[c[x]]=fix[x]=0;
	}
	h.clear();
	ans=min(ans,cn);
	for (int i=0; i<v[center].size(); i++) {
		int to=v[center][i];
		if (!lvl[to]) Build(to,sz/2);
	} 
}

main () {
	cin>>n>>k;
	
	for (int i=1; i<n; i++) {
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	
	for (int i=1; i<=n; i++) {
		cin>>c[i];
		s[c[i]].pb(i);
	}

	Build(1,n);
	--ans;
	cout<<ans<<endl;
}

Compilation message (stderr)

capital_city.cpp: In function 'int Dfs(int, int, int, int&)':
capital_city.cpp:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x].size(); i++) {
                ~^~~~~~~~~~~~
capital_city.cpp: In function 'void Go(int, int)':
capital_city.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x].size(); i++) {
                ~^~~~~~~~~~~~
capital_city.cpp: In function 'void Build(int, int)':
capital_city.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (s[c[x]].size()!=Cf[c[x]]) {
       ~~~~~~~~~~~~~~^~~~~~~~~~
capital_city.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0; i<s[c[x]].size(); i++) 
                  ~^~~~~~~~~~~~~~~
capital_city.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<h.size(); i++) {
                ~^~~~~~~~~
capital_city.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[center].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
capital_city.cpp: At global scope:
capital_city.cpp:73:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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