Submission #217523

#	Time	Username	Problem	Language	Result	Execution time	Memory
217523		super_j6	Capital City (JOI20_capital_city)	C++14	0 / 100	3088 ms	33208 KiB

capital_city

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define endl '\n'
#define pi pair<int, int>

const int maxn = 200000;
int n, m;
int a[maxn], d[maxn], p[maxn], par[maxn], rnk[maxn], sz[maxn], tp[maxn];
bool used[maxn];
vector<int> graph[maxn], cty[maxn];
auto cmp = [&](int x, int y){ return d[x] > d[y];};

int find(int x){
	return x == par[x] ? x : par[x] = find(par[x]);
}

void unionf(int x, int y){
	x = find(x), y = find(y);
	if(x == y) return;
	if(rnk[x] < rnk[y]) swap(x, y);
	if(rnk[x] == rnk[y]) rnk[x];
	par[y] = x;
	sz[x] += sz[y];
	if(d[tp[y]] < d[tp[x]]) tp[x] = tp[y];
}

void dfs(int c){
	for(int i : graph[c]){
		if(i == p[c]) continue;
		p[i] = c;
		d[i] = d[c] + 1;
		dfs(i);
	}
}

int solve(int x){
	used[x] = 1;
	par[x] = x, sz[x] = 1, tp[x] = cty[x][0];
	set<int> h;
	multiset<int, decltype(cmp)> cur(cmp);
	for(int i : cty[x]) cur.insert(i);
	
	int ret = m;
	bool t = 0;
	while(cur.size() > 1){
		int c = *cur.begin();
		cur.erase(cur.begin());
		if(a[p[c]] != x){
			if(!used[a[p[c]]]){
				ret = min(ret, solve(a[p[c]]));
			}else if(h.find(a[p[c]]) == h.end()) t = 1;
			h.insert(a[p[c]]);
			if(tp[find(a[p[c]])] && a[p[tp[find(a[p[c]])]]] == x) cur.insert(tp[find(a[p[c]])]);
			unionf(x, a[p[c]]);
		}else{
			cur.insert(p[c]);
		}
	}
	if(d[*cur.begin()] < d[tp[find(x)]]) tp[find(x)] = *cur.begin();
	if(!t) ret = min(ret, sz[find(x)] - 1);
	
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	
	for(int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		u--, v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i]--;
		cty[a[i]].push_back(i);
	} 
	
	p[0] = -1;
	dfs(0);
	
	int ret = m;
	for(int i = 0; i < m; i++){
		if(!used[i]) ret = min(ret, solve(i));
	}

	cout << ret << endl;

	return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'void unionf(int, int)':
capital_city.cpp:25:28: warning: statement has no effect [-Wunused-value]
  if(rnk[x] == rnk[y]) rnk[x];
                       ~~~~~^

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