Submission #204001

#	Time	Username	Problem	Language	Result	Execution time	Memory
204001		ics0503	Unique Cities (JOI19_ho_t5)	C++17	100 / 100	697 ms	96680 KiB

joi2019_ho_t5

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>edge[212121], L[2][212121]; int color[212121];
int depth[2][212121], D[2][212121], nxtD[2][212121], mx, mxw;
void dfs(int fl, int w, int bef, int dep) {
	depth[fl][w] = dep; D[fl][w] = 0;
	if (mx < dep)mx = dep, mxw = w;
	for (int nxt : edge[w])if (nxt != bef) {
		dfs(fl, nxt, w, dep + 1);
		if (D[fl][w] < D[fl][nxt] + 1)nxtD[fl][w] = nxt;
		D[fl][w] = max(D[fl][w], D[fl][nxt] + 1);
	}
}
int P[2][212121], ans[2][212121], cnt;
int colorCnt, cN[212121];
void coloring(int color, int cnt) {
	int befC = !!cN[color]; cN[color] += cnt;
	if (befC != !!cN[color]) colorCnt += cnt;
}
int eraseC[212121];
void prColor(int fl, int w, int len, int cnt) {
	int now = w;
	for (int i = 0; i < len; i++) {
		if (now < 0)break;
		int befC = !!eraseC[now]; eraseC[now] += cnt;
		if (befC != !!eraseC[now])coloring(color[now], -cnt);
		now = P[fl][now];
	}
}
void get_ans(int fl, int w, int bef, int is_mxline) {
	for (int g : L[fl][w]) if (g > 0) prColor(fl, g, 1, -1);
	P[fl][w] = bef;
	if (bef > 0 && edge[w].size() == 1) {
		ans[fl][w] = colorCnt;
		for (int g : L[fl][w]) if (g > 0) prColor(fl, g, 1, 1);
		return;
	}
	if (!is_mxline) {
		prColor(fl, P[fl][w], D[fl][w], 1);
		int now = w, len = D[fl][w];
		vector<int>z, x, y;
		for (int i = 0; i < len; i++) { if (now > 0)now = P[fl][now]; z.push_back(now); }
		for (int i = len - 1; i >= 0; i--)x.push_back(z[i]);
		x.push_back(w); now = w;
		for (int i = 0; i < len; i++) { now = nxtD[fl][now]; x.push_back(now); y.push_back(now); }
		for (int i = 0, j = 0; i < len; i++, j += 2) {
			int a = y[i], b = x[j], c = x[j + 1];
			L[fl][a].push_back(b); L[fl][a].push_back(c);
		}
	}
	ans[fl][w] = colorCnt;
	coloring(color[w], 1);
	int mx = 0;
	for (int nxt : edge[w]) if (nxt != bef && nxt != nxtD[fl][w]) {
		get_ans(fl, nxt, w, 0);
		if (mx < D[fl][nxt] + 1) mx = D[fl][nxt] + 1;
	}
	prColor(fl, w, 1, 1);

	prColor(fl, P[fl][w], mx, 1);
	get_ans(fl, nxtD[fl][w], w, 1);
	prColor(fl, P[fl][w], mx, -1);

	if (!is_mxline) {
		prColor(fl, P[fl][w], D[fl][w], -1);
	}
	prColor(fl, w, 1, -1); coloring(color[w], -1);

	for (int g : L[fl][w]) if (g > 0) prColor(fl, g, 1, 1);
}
int main() {
	int n, m, i, j; scanf("%d%d", &n, &m);
	if (n == 1) { printf("0"); return 0; }
	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]);
	int l, r;
	mx = mxw = -1; dfs(0, 1, -1, 0); l = mxw;
	mx = mxw = -1; dfs(0, l, -1, 0); r = mxw;
	dfs(1, r, -1, 0);
	get_ans(1, r, -1, 0);
	get_ans(0, l, -1, 0);
	for (i = 1; i <= n; i++) {
		if (depth[0][i] < depth[1][i]) printf("%d\n", ans[1][i]);
		else printf("%d\n", ans[0][i]);
	}
	return 0;
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:74:15: warning: unused variable 'j' [-Wunused-variable]
  int n, m, i, j; scanf("%d%d", &n, &m);
               ^
joi2019_ho_t5.cpp:74:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m, i, j; scanf("%d%d", &n, &m);
                  ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:77:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e; scanf("%d%d", &s, &e);
             ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:80:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= n; i++)scanf("%d", &color[i]);
                          ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32