Submission #112593

#	Time	Username	Problem	Language	Result	Execution time	Memory
112593		Bruteforceman	Mergers (JOI19_mergers)	C++11	100 / 100	1398 ms	126668 KiB

mergers

#include "bits/stdc++.h"
using namespace std;
int city[500010];
int cnt[500010];
vector <int> g[500010];
int P[500010];

int root(int x) {
	if(x == P[x]) return P[x];
	return P[x] = root(P[x]);
}
void join(int x, int y) {
	x = root(x);
	y = root(y);
	if(x != y) {
		P[x] = y;
	}
}

void dfs(int x, int par, map <int, int> &s) {
	if(cnt[city[x]] > 1) {
		s[city[x]] = 1;
	}
	for(auto i : g[x]) {
		if(i - par) {
			map <int, int> t;
			dfs(i, x, t);
			if(t.size() > s.size()) s.swap(t);
			for(auto j : t) {
				s[j.first] += j.second;
				if(cnt[j.first] == s[j.first]) {
					s.erase(j.first);
				} 
			}
		}
	}
	if(!s.empty()) {
		join(x, par);
	}
}

int l[500010], r[500010];
int deg[500010];

int main(int argc, char const *argv[])
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 1; i < n; i++) {
		int p, q;
		scanf("%d %d", &p, &q);
		g[p].push_back(q);
		g[q].push_back(p);
		l[i] = p;
		r[i] = q;
	}
	for(int i = 1; i <= n; i++) {
		scanf("%d", &city[i]);
		cnt[city[i]] += 1;
		P[i] = i; 
	}
	map <int, int> s;
	dfs(1, 0, s);

	set <int> node;
	for(int i = 1; i <= n; i++) {
		node.insert(root(i));
	}
	for(int i = 1; i < n; i++) {
		if(root(l[i]) != root(r[i])) {
			++deg[root(l[i])];
			++deg[root(r[i])];
		}
	}
	int ans = 0;
	for(auto i : node) {
		if(deg[i] <= 1) {
			++ans;
		}
	}
	if(ans > 1) {
		ans = (ans + 1) / 2; 
	} else {
		ans = 0;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main(int, const char**)':
mergers.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &city[i]);
   ~~~~~^~~~~~~~~~~~~~~~

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