Submission #550260

#	Time	Username	Problem	Language	Result	Execution time	Memory
550260		Antekb	Capital City (JOI20_capital_city)	C++14	1 / 100	873 ms	39076 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];
vector<int> co[N];
vector<int> E[N];
void color(int v, int p, int c){
	col[v]=c;
	for(int u:E[v]){
		if(!blo[u] && u!=p){
			color(u, v, c);
		}
	}
}
void dfs(int v){
	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";
	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]){
			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;
}
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])color(u, i, wsk++);
	}
	cout<<ans-1<<"\n";
}

Compilation message (stderr)

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

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