Submission #623483

#	Time	Username	Problem	Language	Result	Execution time	Memory
623483		errorgorn	Capital City (JOI20_capital_city)	C++17	100 / 100	1653 ms	50168 KiB

capital_city

//もう布団の中から出たくない
//布団の外は寒すぎるから
//布団の中から出たくない
//布団の中はあたたかすぎるから

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

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,k;
vector<int> al[200005];
int arr[200005];
vector<int> pos[200005];

int ans=1e9;
int ss[200005];
bool used[200005];

void dfs_ss(int i,int p){
	ss[i]=1;
	for (auto it:al[i]){
		if (it==p || used[it]) continue;
		dfs_ss(it,i);
		ss[i]+=ss[it];
	}
}

int pp[200005];
set<int> s;
void dfs(int i,int p){
	s.insert(i);
	pp[i]=p;
	for (auto it:al[i]){
		if (it==p || used[it]) continue;
		dfs(it,i);
	}
}

bool vis[200005];
bool vis2[200005];

void centroid(int i){
	dfs_ss(i,-1);
	
	int curr=i,currp=-1;
	while (true){
		bool done=true;
		for (auto it:al[curr]){
			if (it==currp || used[it]) continue;
			
			if (ss[it]>=(ss[i]+1)/2){
				currp=curr;
				curr=it;
				done=false;
				break;
			}
		}
		if (done) break;
	}
	
	s.clear();
	dfs(curr,-1);
	
	for (auto it:s) vis[it]=vis2[arr[it]]=false;
	vis[curr]=true;
	vector<int> stk={curr};
	int val=0;
	while (!stk.empty()){
		int u=stk.back(); stk.pob();
		
		if (!vis2[arr[u]]){
			vis2[arr[u]]=true;
			val++;
			
			for (auto it:pos[arr[u]]){
				if (!s.count(it)) goto skip;
				if (!vis[it]){
					vis[it]=true;
					stk.pub(it);
				}
			}
		}
		if (pp[u]!=-1 && !vis[pp[u]]){
			vis[pp[u]]=true;
			stk.pub(pp[u]);
		}
	}
	
	ans=min(ans,val);
	
	skip:;
	
	used[curr]=true;
	for (auto it:al[curr]) if (!used[it]) centroid(it);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>k;
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	rep(x,1,n+1) cin>>arr[x];
	rep(x,1,n+1) pos[arr[x]].pub(x);
	
	centroid(1);
	
	cout<<ans-1<<endl;
}

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