Submission #216886

#	Time	Username	Problem	Language	Result	Execution time	Memory
216886		opukittpceno_hhr	Capital City (JOI20_capital_city)	C++17	41 / 100	1069 ms	39656 KiB

capital_city

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>
#include <functional>

using namespace std;

const int N = 2e5 + 7;

int c[N];
int allcnt[N];
vector<int> g[N];

int used[N];

int sz[N];
int fup[N];
vector<int> bc[N];
vector<int> sn;

void dfs_find(int v, int p, int nsz, int &to) {
	sz[v] = 1;
	int mx = -1;
	for (auto t : g[v]) {
		if (!used[t] && t != p) {
			dfs_find(t, v, nsz, to);
			mx = max(mx, sz[t]);
			sz[v] += sz[t];
		}
	}
	mx = max(mx, nsz - sz[v]);
	if (2 * mx <= nsz) {
		to = v;
	}
}

void dfs_sz(int v, int p) {
	sz[v] = 1;
	for (auto t : g[v]) {
		if (!used[t] && t != p) {
			dfs_sz(t, v);
			sz[v] += sz[t];
		}
	}
}

void dfs_init(int cur, int p) {
	sn.push_back(cur);
	bc[c[cur]].push_back(cur);
	for (auto t : g[cur]) {
		if (!used[t] && t != p) {
			if (c[cur] == c[t]) {
				fup[t] = fup[cur];
			} else {
				fup[t] = cur;
			}
			dfs_init(t, cur);
		}
	}
}

int cans = 0;
int tk[N];

void set_tk(int v) {
	if (tk[c[v]]) return;
	tk[c[v]] = 1;
	cans++;
	if ((int)bc[c[v]].size() < allcnt[c[v]]) {
		cans += N;
	}
	for (auto ov : bc[c[v]]) {
		if (fup[ov] != -1) {
			set_tk(fup[ov]);
		}
	}
}

void dfs_centr(int v, int nsz, int &rans) {
	int cen = -1;
	dfs_find(v, -1, nsz, cen);
	assert(cen != -1);
	used[cen] = 1;
	sn.clear();
	dfs_sz(cen, -1);
	fup[cen] = -1;
	dfs_init(cen, -1);
	cans = 0;
	set_tk(cen);
	rans = min(rans, cans);
	for (auto t : sn) {
		tk[c[t]] = 0;
		bc[c[t]].clear();
	}
	for (auto t : g[cen]) {
		if (used[t]) continue;
		dfs_centr(t, sz[t], rans);
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, k;
	cin >> n >> k;
	for (int i = 0; i + 1 < n; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 0; i < n; i++) {
		cin >> c[i];
		allcnt[c[i]]++;
	}
	int ans = n;
	dfs_centr(0, n, ans);
	cout << ans - 1 << endl;
}

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