Submission #204949

#	Time	Username	Problem	Language	Result	Execution time	Memory
204949		ics0503	Mergers (JOI19_mergers)	C++17	100 / 100	1361 ms	137592 KiB

mergers

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int S[515151], E[515151], dfsCnt = 0, P[515151][21], depth[515151];
vector<int>edge[515151];
void dfs(int w, int bef, int dep) {
	S[w] = ++dfsCnt; P[w][0] = bef; depth[w] = dep;
	for (int i = 0; P[w][i] != -1; i++)P[w][i + 1] = P[P[w][i]][i];
	for (int nxt : edge[w]) if (nxt != bef)dfs(nxt, w, dep + 1);
	E[w] = dfsCnt;
}
void go_up(int &x, int y) { for (int i = 0; i < 20; i++)if (y&(1 << i))x = P[x][i]; }
int get_lca(int a, int b) {
	if (depth[a] < depth[b])go_up(b, depth[b] - depth[a]);
	if (depth[a] > depth[b])go_up(a, depth[a] - depth[b]);
	if (a == b)return a;
	for (int i = 19; i >= 0; i--) if(P[a][i] != P[b][i]) { a = P[a][i]; b = P[b][i]; }
	return P[a][0];
}
vector<pair<int, int>>L[515151];
int up[515151];
void dfs_uf(int w, int bef) {
	for (int nxt : edge[w]) if (nxt != bef) {
		dfs_uf(nxt, w);
		up[w] = min(up[w], up[nxt]);
	}
}
int par[515151];
int find(int x) {
	if (par[x] == x)return x;
	return par[x] = find(par[x]);
}
int indeg[515151];

int main() {
	int n, k, 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++)for (j = 0; j < 20; j++)P[i][j] = -1;
	dfs(1, -1, 1);
	for (i = 1; i <= n; i++) {
		int color; scanf("%d", &color);
		L[color].push_back({ S[i], i });
	}
	for (i = 1; i <= n; i++)up[i] = 1e9;
	for (i = 1; i <= k; i++) {
		sort(L[i].begin(), L[i].end());
		for (j = 0; j < L[i].size() - 1; j++){
			int a = L[i][j].second, b = L[i][j + 1].second;
			int lca = get_lca(a, b);
			up[a] = min(up[a], depth[lca]);
			up[b] = min(up[b], depth[lca]);
		}
	}
	dfs_uf(1, -1);
	for (i = 1; i <= n; i++)par[i] = i;
	for (i = 1; i <= n; i++) if (depth[i] > up[i])par[find(i)] = find(P[i][0]);
	for (i = 1; i <= n; i++) {
		int s = i;
		for (int e : edge[s]) {
			int ps = find(s), pe = find(e);
			if (ps==pe)continue;
			indeg[ps]++; indeg[pe]++;
		}
	}
	int res = 0;
	for (i = 1; i <= n; i++)if (par[i] == i) {
		if (indeg[i] <= 2)res++;
	}
	if (res == 1)printf("0");
	else printf("%d", (res + 1) / 2);
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:51:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < L[i].size() - 1; j++){
               ~~^~~~~~~~~~~~~~~~~
mergers.cpp:37:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, k, i, j; scanf("%d%d", &n, &k);
                  ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:39: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);
             ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:45:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int color; scanf("%d", &color);
              ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30