Submission #102476

#	Time	Username	Problem	Language	Result	Execution time	Memory
102476		AngusRitossa	Mergers (JOI19_mergers)	C++14	100 / 100	1553 ms	154716 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
	#define D(x...) printf(x)
#else
	#define D(x...)
#endif
int n, k, amof[500010], c[500010];
vector<int> adj[500010];
int leaves;
int last;
map<int, int>* ms[500010];
int dfs(int a, int p = -1)
{
	int ambadchildren = 0;
	ms[a] = new map<int, int>();

	(*ms[a])[c[a]]++;
	if ((*ms[a])[c[a]] == amof[c[a]]) ms[a]->erase(c[a]);

	for (auto b : adj[a])
	{
		if (b != p) 
		{
			int am = dfs(b, a);
			ambadchildren += am;

			if (ms[b]->size() > ms[a]->size()) swap(ms[a], ms[b]);
			for (auto c : *ms[b])
			{
				(*ms[a])[c.first]+=c.second;
				if ((*ms[a])[c.first] == amof[c.first]) ms[a]->erase(c.first);
			}
		}
	}
	last = max(last, ambadchildren);
	if (p != -1)
	{
		int old = ambadchildren;
		ambadchildren = !ms[a]->size();
		D("%d %d\n", a, ambadchildren);
		if (ambadchildren) last = 1;
		if (!old) leaves += ambadchildren;
		else ambadchildren = old;
	}
	else if (p == -1 && ambadchildren == 1)
	{
		leaves += last == 1;
	}	
	return !!ambadchildren;
}	
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i < n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) scanf("%d", &c[i]), amof[c[i]]++;
	dfs(1);
	D("%d\n", leaves);
	printf("%d\n", (leaves+1)/2);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:62:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d", &c[i]), amof[c[i]]++;
                               ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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