Submission #246082

#	Time	Username	Problem	Language	Result	Execution time	Memory
246082		onjo0127	Capital City (JOI20_capital_city)	C++11	100 / 100	1274 ms	35708 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int C[200009], pr[200009], sb[200009], stt[200009], ans = INF;
vector<int> G[200009], S[200009];
bool chk[200009], use[200009];

void dfs(int x, int p) {
	pr[x] = p;
	sb[x] = 1;
	for(auto& it: G[x]) if(it != p && !chk[it]) {
		dfs(it, x);
		sb[x] += sb[it];
	}
}

int cent(int rt) {
	int x = rt, p = rt;
	while(1) {
		int mxi = -1;
		for(auto& it: G[x]) if(it != p && !chk[it]) {
			if(mxi == -1 || sb[mxi] < sb[it]) mxi = it;
		}
		if(mxi == -1 || sb[mxi]*2 <= sb[rt]) return x;
		p = x; x = mxi;
	}
}

void col(int x, int p, int c) {
	stt[x] = c;
	for(auto& it: G[x]) if(it != p && !chk[it]) col(it, x, c);
}

void go(int rt) {
	col(rt, rt, 2);
	dfs(rt, rt);
	int ctr = cent(rt);
	dfs(ctr, ctr);
	vector<int> U;
	queue<int> que; que.push(C[ctr]);
	use[C[ctr]] = 1; U.push_back(C[ctr]);
	while(que.size()) {
		int nc = que.front(); que.pop();
		for(auto& it: S[nc]) {
			int x = it;
			if(stt[x] == 0) goto abt;
			while(pr[x] != x) {
				if(stt[x] == 0) goto abt;
				if(stt[x] == 1) break;
				stt[x] = 1;
				if(!use[C[x]]) {
					use[C[x]] = 1;
					U.push_back(C[x]);
					que.push(C[x]);
				}
				x = pr[x];
			}
		}
	}
	ans = min(ans, (int)U.size() - 1);
	abt:
	for(auto& it: U) use[it] = 0;
	col(rt, rt, 0);
	chk[ctr] = 1;
	for(auto& it: G[ctr]) if(!chk[it]) go(it);
}

int main() {
	int N, K; scanf("%d%d", &N, &K);
	for(int i=0; i<N-1; i++) {
		int u, v; scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1; i<=N; i++) {
		scanf("%d", &C[i]);
		S[C[i]].push_back(i);
	}
	go(1);
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:70:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, K; scanf("%d%d", &N, &K);
            ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d",&u,&v);
             ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &C[i]);
   ~~~~~^~~~~~~~~~~~~

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