Submission #667166

#	Time	Username	Problem	Language	Result	Execution time	Memory
667166		Kahou	Capital City (JOI20_capital_city)	C++14	11 / 100	1264 ms	524288 KiB

capital_city

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5 + 50;
int n, k, c[N], sub[N], sz[N];
bool flg[N];

map<int, int> mp[N];
vector<int> adj[N];
vector<int> adjP[N], adjM[N];
int id[N], scz[N];
vector<int> vc;
bool vis[N];

void dfs(int u, int p) {
	for (int v:adj[u]) {
		if (v == p) continue;

		dfs(v, u);

		for (pii x:mp[v]) {
			if (x.S < sz[x.F] && x.F != c[u]) {
				adjP[x.F].push_back(c[u]);
				adjM[c[u]].push_back(x.F);
			}
			mp[u][x.F] += x.S;
		}
	}
	mp[u][c[u]]++;
}

void dfs2(int u) {
	vis[u] = 1;
	for (int v:adjP[u]) {
		if (vis[v]) continue;
		dfs2(v);
	}
	vc.push_back(u);
}
void sfd(int u) {
	scz[id[u]]++;
	for (int v:adjM[u]) {
		if (id[v]) continue;
		id[v] = id[u];
		sfd(v);
	}
}
void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n-1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int u = 1; u <= n; u++) {
		cin >> c[u];
		sz[c[u]]++;
	}
	dfs(1, 0);
	for (int u = 1; u <= k; u++) {
		sort(adjP[u].begin(), adjP[u].end());
		adjP[u].resize(unique(adjP[u].begin(), adjP[u].end())-adjP[u].begin());
		sort(adjM[u].begin(), adjM[u].end());
		adjM[u].resize(unique(adjM[u].begin(), adjM[u].end())-adjM[u].begin());
	}
	for (int u = 1; u <= k; u++) {
		if (!vis[u]) dfs2(u);
	}
	reverse(vc.begin(), vc.end());
	for (int u:vc) {
		if (!id[u]) {
			flg[u] = 1;
			id[u] = u;
			sfd(u);
		}
	}
	int ans = 1e9;
	for (int u:vc) {
		for (int v:adjP[u]) {
			flg[id[u]] = flg[id[u]]&&(id[v] == id[u]);
		}
	}
	for (int u:vc) {
		if (flg[id[u]]) ans = min(ans, scz[id[u]]);
	}
	cout << ans-1 << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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