Submission #242097

#	Time	Username	Problem	Language	Result	Execution time	Memory
242097		ZwariowanyMarcin	Capital City (JOI20_capital_city)	C++14	100 / 100	963 ms	39660 KiB

capital_city

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
 
using namespace std;

const int N = 2e5 + 101;

int n, k, a, b, res = 1e9;
vector <int> g[N], x;
bool dead[N], vis[N];
int siz[N], color[N], total[N], par[N], last[N], id;
vector <int> q[N];

void licz(int v, int p) {
	siz[v] = 1;
	for (auto it : g[v])
		if (!dead[it] && it != p) {
			licz(it, v);
			siz[v] += siz[it];
		}
}

int daj(int v, int p, int all) {
	for (auto it : g[v])
		if (!dead[it] && it != p && all < 2 * siz[it])
			return daj(it, v, all);
	return v;
}

void dfs(int v, int p) {
	x.pb(v);
	q[color[v]].pb(v);
	par[v] = p;
	for (auto it : g[v])
		if (!dead[it] && it != p)
			dfs(it, v);
}

vector <int> stos;
bool bad;
int now;

void add(int c) {
	if (last[c] == id) return;
	if (total[c] != ss(q[c])) bad = true;
	last[c] = id;
	now++;
	stos.pb(c);
}

void dek(int v) {
	licz(v, 0);
	int cen = daj(v, 0, siz[v]);
	// process cen
	dfs(cen, 0);
	++id;
	bad = false;
	now = 0;
	add(color[cen]);
	while (!stos.empty()) {
		int k = stos.back();
		stos.pop_back();
		for (auto it : q[k]) {
			int s = it;
			while (s != 0 && !vis[s]) {
				vis[s] = true;
				add(color[s]);
				s = par[s];
			}
		}
	}
	if (!bad) res = min(res, now);
	for (auto it : x) {
		q[color[it]].clear();
		vis[it] = false;
	}
	x.clear();
	dead[cen] = true;
	for (auto it : g[cen])
		if (!dead[it])
			dek(it);
	
}

int main() {
	scanf ("%d%d", &n, &k);
	rep(i, 2, n) {
		scanf ("%d%d", &a, &b);
		g[a].pb(b);
		g[b].pb(a);
	}
	rep(i, 1, n) {
		scanf ("%d", color + i);
		total[color[i]]++;
	}
	dek(1);
	printf ("%d\n", res - 1);
	return 0;
}	

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &k);
  ~~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:98:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", color + i);
   ~~~~~~^~~~~~~~~~~~~~~~~

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