Submission #261109

#	Time	Username	Problem	Language	Result	Execution time	Memory
261109		amoo_safar	Capital City (JOI20_capital_city)	C++17	100 / 100	793 ms	37428 KiB

capital_city

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int n, K, col[N], ans = N;
vector<int> G[N], C[N];
int mkc[N], Tc = 1;
int slv[N], mk[N], Tm, vis[N], Tv;
int sub[N], par[N];

int Sub(int u, int p){
	sub[u] = 1;
	vis[u] = Tv;
	//par[u] = p;
	for(auto adj : G[u])
		if(adj != p && !slv[adj])
			sub[u] += Sub(adj, u);
	return sub[u];
}
void Par(int u, int p){
	par[u] = p;
	for(auto adj : G[u]){
		if(adj != p && !slv[adj])
			Par(adj, u);
	}
}

int Q[N];
void Solve(int u){
	Tv ++;
	int sz = Sub(u, -1);
	int cen = u;
	bool fnd = false;
	while(!fnd){
		fnd = true;
		for(auto adj : G[cen]){
			if(!slv[adj] && sub[adj] < sub[cen] && 2*sub[adj] >= sz){
				fnd = false;
				cen = adj;
				break;
			}
		}
	}
	Par(cen, -1);
	//cerr << u << " -> " << cen << '\n';
	int l = 0, r = 1;
	Q[0] = cen; 
	int fr, res = 0; Tc ++; Tm ++;
	mk[cen] = Tm;
	while(l < r){
		fr = Q[l]; l++;
		//if(cen == 3) debug(fr);
		if(mkc[col[fr]] != Tc){
			res ++;

			mkc[col[fr]] = Tc;
			for(auto adj : C[col[fr]]){
				if(vis[adj] != Tv){
					res = N;
					break;
				}
				if(mk[adj] != Tm){
					Q[r ++] = adj;
					mk[adj] = Tm;
				}
			}
		}
		if(par[fr] != -1 && mk[par[fr]] != Tm){
			mk[par[fr]] = Tm;
			Q[r ++] = par[fr];
		}
	}
	ans = min(ans, res - 1);
	slv[cen] = 1;
	for(auto adj : G[cen]) if(!slv[adj]) Solve(adj);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> K;
	int u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	for(int i = 1; i <= n; i++){
		cin >> col[i];
		C[col[i]].pb(i);
	}
	//cerr << '\n';
	Solve(1);
	cout << ans << '\n';
	return 0;
}
/*
6 3
2 1
3 5
6 2
3 4
2 3
1
3
1
2
3
2
*/

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