제출 #355601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
355601		Fischer	Mergers (JOI19_mergers)	C++14	100 / 100	1519 ms	144248 KiB

mergers

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;
vector<int> g[maxn];
vector<int> color[maxn];
const int maxlog = 18;
int st[maxn][maxlog];
int lo[maxn], h[maxn];
int T;

void dfs(int x, int p=-1) {
	lo[x] = T++;
	h[x] = (~p ? h[p] + 1 : 0);
	st[x][0] = (~p ? p : x);
	for (int k = 1; k < maxlog; ++k) {
		st[x][k] = st[st[x][k-1]][k-1];
	}
	for (int v : g[x]) {
		if (v == p) continue;
		dfs(v, x);
	}
}

int lca(int x, int y) {
	if (h[x] > h[y]) swap(x, y);
	for (int i = maxlog-1; i >= 0; --i) {
		if (h[st[y][i]] >= h[x]) {
			y = st[y][i];
		}
	}
	if (x == y) return x;
	for (int i = maxlog-1; i >= 0; --i) {
		if (st[x][i] != st[y][i]) {
			x = st[x][i];
			y = st[y][i];
		}
	}
	return st[x][0];
}

int link[maxn];
int rnk[maxn];

int get(int x) {
	return x == link[x] ? x : link[x] = get(link[x]);
}

void merge(int x, int y) {
	x = get(x);
	y = get(y);
	if (x == y) return;
	if (rnk[x] < rnk[y]) swap(x, y);
	rnk[x] += rnk[x] == rnk[y];
	link[y] = x;
}

vector<pair<int, int>> edges;
int dp[maxn], deg[maxn];
void dfs_in_out(int x, int p=-1) {
	for (int v : g[x]) {
		if (v == p) continue;
		dfs_in_out(v, x);
		dp[x] += dp[v];
	}
	if (~p) {
		if (dp[x] == 0) {
			edges.push_back({x, p});
		} else {
			merge(x, p);
		}
	}
}

int main() {
	int n, k;
	cin >> n >> k; 
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 1; i <= n; ++i) {
		int d;
		cin >> d;
		color[d].push_back(i);
	}
	dfs(1);
	for (int d = 1; d <= k; ++d) {
		sort(color[d].begin(), color[d].end(), [&](int u, int v) {
			return lo[u] < lo[v];	
		});
		for (int j = 1; j < color[d].size(); ++j) {
			int u = color[d][j-1], v = color[d][j];
			int t = lca(u, v);
			dp[u] += 1;
			dp[v] += 1;
			dp[t] -= 2;
		}
	}
	for (int i = 1; i <= n; ++i) {
		link[i] = i;
		rnk[i] = 0;
	}
	dfs_in_out(1);
	for (auto e : edges) {
		int u = e.first, v = e.second;
		deg[get(u)] += 1;
		deg[get(v)] += 1;
	}
	int leaves = 0;
	for (int i = 1; i <= n; ++i) {
		if (deg[i] == 1 && get(i) == i) {
			leaves += 1;
		}	
	}
	cout << (leaves + 1) / 2 << endl;
	return 0;
}

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

mergers.cpp: In function 'int main()':
mergers.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int j = 1; j < color[d].size(); ++j) {
      |                   ~~^~~~~~~~~~~~~~~~~

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