Submission #446872

#	Time	Username	Problem	Language	Result	Execution time	Memory
446872		ics0503	Capital City (JOI20_capital_city)	C++17	100 / 100	1069 ms	43708 KiB

capital_city

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<deque>
using namespace std;

int n, k;
vector<int>edge[212121], color_list[212121];
int color[212121], ans = 1e9, complete[212121];
int sz[212121];
void get_sz(int w, int bef) {
	sz[w] = 1;
	for (int nxt : edge[w]) {
		if (complete[nxt])continue;
		if (nxt == bef)continue;
		get_sz(nxt, w);
		sz[w] += sz[nxt];
	}
}
int get_cent(int w, int bef, int all_sz) {
	for (int nxt : edge[w]) {
		if (complete[nxt])continue;
		if (nxt == bef)continue;
		if (all_sz / 2 < sz[nxt]) {
			return get_cent(nxt, w, all_sz);
		}
	}
	return w;
}
int before[212121];
void get_bef(int w, int bef) {
	before[w] = bef;
	for (int nxt : edge[w]) {
		if (complete[nxt])continue;
		if (nxt == bef)continue;
		get_bef(nxt, w);
	}
}
int ck[212121], is_color_in[212121], color_cnt[212121];
vector<int>temp_L;
void counting_color(int w, int bef) {
	if (color[w] > 0) {
		color_cnt[color[w]]++;
		temp_L.push_back(color[w]);
	}
	for (int nxt : edge[w]) {
		if (nxt == bef)continue;
		if (complete[nxt])continue;
		counting_color(nxt, w);
	}
}
void disable_vertex(int w, int bef) {
	int w_col = color[w];
	if (w_col > 0) {
		if (color_list[w_col].size() != color_cnt[w_col]) {
			color[w] = -1;
		}
	}
	for (int nxt : edge[w]) {
		if (nxt == bef)continue;
		if (complete[nxt])continue;
		disable_vertex(nxt, w);
	}
}

void centroid_decomposition(int x) {
	get_sz(x, -1);
	int cent = get_cent(x, -1, sz[x]);
	get_bef(cent, -1);
	if (color[cent] != -1) {
		vector<int>Q, L, CL;
		Q.push_back(color[cent]);
		is_color_in[color[cent]] = 1; CL.push_back(color[cent]);
		int res = 0, fk = 0;
		while (!Q.empty()) {
			int q_col = Q.back(); Q.pop_back();
			res++;
			for (int v : color_list[q_col]) {
				int now = v;
				while (now > 0 && ck[now] == 0) {
					ck[now] = 1; L.push_back(now);
					int now_col = color[now];
					if (now_col == -1) {
						fk = 1;
						break;
					}
					if (!is_color_in[now_col]) {
						is_color_in[now_col] = 1;
						Q.push_back(now_col); CL.push_back(now_col);
					}
					now = before[now];
				}
				if (fk)break;
			}
			if (fk)break;
		}
		for (int x : CL)is_color_in[x] = 0;
		for (int x : L)ck[x] = 0;
		if (!fk) ans = min(res - 1, ans);
	}
	complete[cent] = 1;
	for (int nxt : edge[cent]) {
		if (complete[nxt])continue;
		counting_color(nxt, -1);
		disable_vertex(nxt, -1);
		for (auto v : temp_L)color_cnt[v] = 0;
		temp_L.clear();
	}
	for (int nxt : edge[cent]) {
		if (complete[nxt])continue;
		centroid_decomposition(nxt);
	}
}

int main() {
	int i, j;
	scanf("%d%d", &n, &k);
	for (i = 0; i < n - 1; i++) {
		int s, e; scanf("%d%d", &s, &e);
		edge[s].push_back(e);
		edge[e].push_back(s);
	}
	for (i = 1; i <= n; i++) {
		scanf("%d", &color[i]);
		color_list[color[i]].push_back(i);
	}
	centroid_decomposition(1);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'void disable_vertex(int, int)':
capital_city.cpp:55:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if (color_list[w_col].size() != color_cnt[w_col]) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:116:9: warning: unused variable 'j' [-Wunused-variable]
  116 |  int i, j;
      |         ^
capital_city.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:119:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   int s, e; scanf("%d%d", &s, &e);
      |             ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |   scanf("%d", &color[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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