Submission #550264

#	Time	Username	Problem	Language	Result	Execution time	Memory
550264		Antekb	Capital City (JOI20_capital_city)	C++14	100 / 100	824 ms	46808 KiB

capital_city

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int blo[N], col[N], par[N], vis[N], typ[N], siz[N];
vector<int> co[N];
vector<int> E[N];
int cent;
void color(int v, int p, int c, int n){
	col[v]=c;
	bool czy=1;
	siz[v]=1;
	for(int u:E[v]){
		if(!blo[u] && u!=p){
			color(u, v, c, n);
			siz[v]+=siz[u];
			if(siz[u]*2>n)czy=0;
		}
	}
	if(siz[v]*2<n)czy=0;
	if(czy)cent=v;
}
void dfs(int v){
	//cout<<v<<" "<<par[v]<<col[v]<<" "<<typ[v]<<"q\n";
	for(int u:E[v]){
		if(u!=par[v] && !blo[u]){
			par[u]=v;
			dfs(u);
		}
	}
}
int wsk=1;
int ans=N;
void solve(int v, int id){
	//cout<<v<<" "<<id<<"\n";
	/*for(int u=1; u<=12; u++)if(col[u]==id){
		assert(!blo[u]);
		cout<<u<<" ";
	}
		cout<<"\n";*/
	par[v]=0;
	dfs(v);
	vector<int> V;
	V.push_back(typ[v]);
	vis[typ[v]]=1;
	for(int i=0; i<V.size(); i++){
		int c=V[i];
		for(int v:co[c]){
			//cout<<v<<" "<<col[v]<<" "<<typ[v]<<"\n";
			if(col[v]!=id){
				for(int u:V)vis[u]=0;
				return;
			}
			if(par[v] && !vis[typ[par[v]]]){
				vis[typ[par[v]]]=1;
				V.push_back(typ[par[v]]);
			}
		}
	}
	//cout<<V.size()<<"\n";
	ans=min(ans, (int)V.size());
	for(int u:V)vis[u]=0;
}
void rek(int v, int n){
	cent=v;
	color(v, 0, wsk++, n);
	solve(cent, col[cent]);
	blo[cent]=1;
	for(int u:E[cent])if(!blo[u])rek(u, siz[u]);
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main(){
	int n, k;
	cin>>n>>k;
	for(int i=1; i<n; i++){
		int u, v;
		cin>>u>>v;
		E[u].push_back(v);
		E[v].push_back(u);
	}
	for(int i=1; i<=n; i++){
		cin>>typ[i];
		co[typ[i]].push_back(i);
	}
	vector<int> kol;
	for(int i=1; i<=n; i++)kol.push_back(i);
	/*shuffle(kol.begin(), kol.end(), rng);
	for(int i:kol){
		solve(i, col[i]);
		blo[i]=1;
		for(int u:E[i])if(!blo[u])color(u, i, wsk++);
	}*/
	rek(1, n);
	cout<<ans-1<<"\n";
}

Compilation message (stderr)

capital_city.cpp: In function 'void solve(int, int)':
capital_city.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

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