Submission #920878

#	Time	Username	Problem	Language	Result	Execution time	Memory
920878		yellowtoad	Mergers (JOI19_mergers)	C++17	100 / 100	1611 ms	180580 KiB

mergers

#include <iostream>
#include <vector>
using namespace std;

int n, k, p[500010][20], d[500010], vis[500010], cnt, ans;
vector<int> edge[500010], a[500010], adj[500010], tmp, ed[500010];

void build(int u, int v, int depth) {
	adj[u].push_back(v);
	p[u][0] = v;
	d[u] = depth;
	for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i-1]][i-1];
	for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) build(edge[u][i],u,depth+1);
}

int lca(int u, int v) {
	if (d[u] < d[v]) swap(u,v);
	int i = 19;
	while (i >= 0) {
		if (d[p[u][i]] >= d[v]) u = p[u][i];
		i--;
	}
	if (u == v) return u;
	i = 19;
	while (i >= 0) {
		if (p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
		i--;
	}
	return p[u][0];
}

void dfs(int u) {
	vis[u] = cnt;
	for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != p[u][0]) tmp.push_back(edge[u][i]);
	for (int i = 0; i < adj[u].size(); i++) if (!vis[adj[u][i]]) dfs(adj[u][i]);
}

int main() {
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		int u;
		cin >> u;
		a[u].push_back(i);
	}
	build(1,0,1);
	for (int i = 1; i <= k; i++) {
		int lcaa = a[i][0];
		for (int j = 1; j < a[i].size(); j++) lcaa = lca(lcaa,a[i][j]);
		for (int j = 0; j < a[i].size(); j++) adj[lcaa].push_back(a[i][j]);
	}
	tmp.push_back(1);
	while (tmp.size()) {
		int u = tmp.back();
		tmp.pop_back();
		if (vis[u]) continue;
		cnt++;
		dfs(u);
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i] != vis[p[i][0]]) {
			ed[vis[p[i][0]]].push_back(vis[i]);
			ed[vis[i]].push_back(vis[p[i][0]]);
		}
	}
	for (int i = 1; i <= cnt; i++) if (ed[i].size() <= 1) ans++;
	if (cnt == 1) cout << 0 << endl;
	else cout << (ans+1)/2 << endl;
}

Compilation message (stderr)

mergers.cpp: In function 'void build(int, int, int)':
mergers.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) build(edge[u][i],u,depth+1);
      |                  ~~^~~~~~~~~~~~~~~~
mergers.cpp: In function 'void dfs(int)':
mergers.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != p[u][0]) tmp.push_back(edge[u][i]);
      |                  ~~^~~~~~~~~~~~~~~~
mergers.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 0; i < adj[u].size(); i++) if (!vis[adj[u][i]]) dfs(adj[u][i]);
      |                  ~~^~~~~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int j = 1; j < a[i].size(); j++) lcaa = lca(lcaa,a[i][j]);
      |                   ~~^~~~~~~~~~~~~
mergers.cpp:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for (int j = 0; j < a[i].size(); j++) adj[lcaa].push_back(a[i][j]);
      |                   ~~^~~~~~~~~~~~~

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