Submission #366851

#	Time	Username	Problem	Language	Result	Execution time	Memory
366851		minoum	Capital City (JOI20_capital_city)	C++17	100 / 100	803 ms	42856 KiB

capital_city

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 2e5+5, inf = INT_MAX/4;
int n, k, c[MAXN], ans[MAXN], mark[MAXN], cm = 0, par[MAXN], sz[MAXN], m;
vector <int> adj[MAXN], all[MAXN], clr, clrc;
bool dead[MAXN], visi[MAXN], inc[MAXN];

void dfs(int v, int parv){
 	m++; sz[v] = 1;
	for(int u: adj[v]){
		if(!dead[u] && u != parv){
			par[u] = v;
			dfs(u, v);
			sz[v] += sz[u];
		}
	}
	return;
}

inline int findcentroid(int v){
	int cent = v; par[v] = -1; m = 0;
	dfs(v, -1); 
	bool f = false; 
	while(!f){
		f = true;
		for(int u: adj[cent]){
			if(!dead[u] && u != par[cent] && sz[u] >= (m / 2)){
				f = false;
				cent = u;
				break;
			}
		}
	}
	return cent;
}

void dfs2(int v, int parv){
	mark[v] = cm;
	for(int u: adj[v])
		if(!dead[u] && u!=parv){
			par[u] = v;
			dfs2(u,v);
		} 
	return;
}

void calc(int r){
	while(!clr.empty()){
		visi[clr.back()] = false; clr.pop_back();
	}
	while(!clrc.empty()){
		inc[clrc.back()] = false; clrc.pop_back();
	}
	queue <int> q;
	for(int i: all[c[r]]){
		if(mark[i] != cm){
			ans[r] = inf;
			return;
		}
		q.push(i);
	}
	clrc.push_back(c[r]); inc[c[r]] = true;
	while(!q.empty()){
		int v = q.front(); q.pop();
		while(v!=-1 && !visi[v]){
			visi[v] = true; clr.push_back(v);
		//	cout << "v:" << v+1 << "  parv:" << par[v]+1 << endl;
			if(!inc[c[v]]){
//				cout << "IIFFFF   " << c[v] << endl;
				for(int i: all[c[v]]){
					if(mark[i] != cm){
						ans[r] = inf;
						return;
					}
					if(i!=v && !visi[i]) q.push(i);
				}
				clrc.push_back(c[v]); inc[c[v]] = true; ans[r]++;
			}
			v = par[v];
		}
	}
	return;
}

void slv(int v){
	int cent = findcentroid(v);
	cm++; par[cent] = -1; dfs2(cent,-1);
	calc(cent);
//	cout << "cent:" << cent+1 << "  ans:" << ans[cent] << endl;
	dead[cent] = true;
	for(auto u: adj[cent])
		if(!dead[u]) slv(u);
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for(int i = 0; i < n-1; i++){
		int u, v;
		cin >> u >> v; u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 0; i < n; i++){
		cin >> c[i];
		all[c[i]].push_back(i);
	}
	slv(0);
	int aans = inf;
	for(int i = 0; i < n; i++) aans = min(aans, ans[i]);
	cout << aans << '\n';
	return 0; 
}

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