Submission #377938

#	Time	Username	Problem	Language	Result	Execution time	Memory
377938		casperwang	Mergers (JOI19_mergers)	C++14	0 / 100	186 ms	70232 KiB

mergers

#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
 
const int MAXN = 500000;
int n, k;
int a, b;
vector <int> path[MAXN+1];
int clr[MAXN+1];
int cnt_clr[MAXN+1];
unordered_map <int,int> cnt[MAXN+1];
int full[MAXN+1];
int dsu[MAXN+1];
vector <int> G[MAXN+1];
int leaves;

int fnd(int a) {
	return a == dsu[a] ? a : dsu[a] = fnd(dsu[a]);
}

void Merge(int a, int b) {
	a = fnd(a), b = fnd(b);
	dsu[a] = b;
}

void DFS(int now, int par) {
	cnt[now][clr[now]]++;
	if (cnt_clr[clr[now]] == 1)
		full[now]++;
	for (int i : path[now]) {
		if (i == par) continue;
		DFS(i, now);
		if (cnt[i].size() > cnt[now].size())
			swap(cnt[now], cnt[i]);
		full[now] += full[i];
		for (auto [v, c] : cnt[i]) {
			cnt[now][v] += c;
			if (cnt[now][v] == cnt_clr[v])
				full[now]++;
		}
	}
	if (full[now] != cnt[now].size())
		Merge(now, par);
}
 
signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		path[a].pb(b);
		path[b].pb(a);
	}
	for (int i = 1; i <= n; i++) {
		cin >> a;
		clr[i] = a;
		cnt_clr[a]++;
		dsu[i] = i;
	}
	DFS(1, 0);
	for (int i = 1; i <= n; i++) {
		for (int j : path[i]) {
			if (fnd(i) != fnd(j)) {
				G[fnd(i)].pb(fnd(j));
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!G[i].size()) continue;
		bool flag = true;
		for (int j : G[i]) {
			flag &= (j == G[i][0]);
		}
		if (flag)
			leaves++;
	}
	cout << (leaves+1)/2 << '\n';
}

Compilation message (stderr)

mergers.cpp: In function 'void DFS(int, int)':
mergers.cpp:40:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |   for (auto [v, c] : cnt[i]) {
      |             ^
mergers.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  if (full[now] != cnt[now].size())
      |      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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