제출 #203983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
203983		ics0503	Unique Cities (JOI19_ho_t5)	C++17	4 / 100	2080 ms	36840 KiB

joi2019_ho_t5

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>edge[212121]; int color[212121], depth[2][212121], D[2][212121], mx, mxw;
void dfs(int fl, int w, int bef, int dep) {
	D[fl][w] = depth[fl][w] = dep;
	if (mx < dep)mx = dep, mxw = w;
	for (int nxt : edge[w])if (nxt != bef) {
		dfs(fl, nxt, w, dep + 1);
		D[fl][w] = max(D[fl][w], D[fl][nxt]);
	}
}
int P[2][212121], ans[2][212121], cnt, colorCnt, cN[212121], prC[212121];
void coloring(int color, int cnt) {
	int befC = !!cN[color]; cN[color] += cnt;
	if (befC != !!cN[color]) colorCnt += cnt;
}
void prColor(int fl, int w, int len, int cnt) {
	int now = w;
	for (int i = 0; i < len; i++) if (now > 0) {
		int befC = !!prC[now]; prC[now] += cnt;
		if (befC != !!prC[now])coloring(color[now], -cnt);
		now = P[fl][now];
	}
}
void get_ans(int fl, int w, int bef) {
	P[fl][w] = bef; vector<pair<int, int>>L;
	for (int nxt : edge[w]) if (nxt != bef) L.push_back({ -(D[fl][nxt] - depth[fl][w]), nxt });
	sort(L.begin(), L.end());
	if (L.size() == 0) { ans[fl][w] = colorCnt; return; }
	int mx = -L.front().first; prColor(fl, P[fl][w], mx, 1);
	ans[fl][w] = colorCnt;
	coloring(color[w], 1);
	
	for (int i = 1; i < L.size(); i++) get_ans(fl, L[i].second, w);
	prColor(fl, P[fl][w], mx, -1);

	mx = (L.size() > 1)? -L[1].first: 0; prColor(fl, P[fl][w], mx, 1);
	get_ans(fl, L[0].second, w);
	prColor(fl, P[fl][w], mx, -1);

	coloring(color[w], -1);
}
int main() {
	int n, m, i, j, l, r; scanf("%d%d", &n, &m);
	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]);
	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(0, l, -1); get_ans(1, r, -1);
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t5.cpp: In function 'void get_ans(int, int, int)':
joi2019_ho_t5.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < L.size(); i++) get_ans(fl, L[i].second, w);
                  ~~^~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:46:15: warning: unused variable 'j' [-Wunused-variable]
  int n, m, i, j, l, r; scanf("%d%d", &n, &m);
               ^
joi2019_ho_t5.cpp:46:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m, i, j, l, r; scanf("%d%d", &n, &m);
                        ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:48: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:51: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: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32