Submission #987111

#	Time	Username	Problem	Language	Result	Execution time	Memory
987111		OAleksa	Mergers (JOI19_mergers)	C++14	70 / 100	1593 ms	262144 KiB

mergers

#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N = 5e5 + 69;
const int K = 20;
int n, k, a[N], ans, cc[N], is[N], have[N];
vector<int> g[N], c[N];
vector<int> t[N];
map<int, int> cnt[N];
void dfs(int v, int p) {
	cnt[v][a[v]] = 1;
	if (c[a[v]].size() == 1)
		have[v] = 1;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
		int o = have[v];
		if (cnt[u].size() > cnt[v].size()) {
			have[v] += have[u];
			swap(cnt[u], cnt[v]);
		}
		else
			o = 0;
		for (auto j : cnt[u]) {
			cnt[v][j.f] += j.s;
			have[v] += (cnt[v][j.f] == (int)c[j.f].size());
		}
		have[v] -= o;
	}
	assert(have[v] <= cnt[v].size());
	if (have[v] == cnt[v].size())
		cc[v] = 1;
}
void build(int v, int p, int c) {
	int x = c;
	if (cc[v] && v > 1) {
		t[v].push_back(c);
		t[c].push_back(v);
		x = v;
	}
	for (auto u : g[v]) {
		if (u == p)
			continue;
		build(u, v, x);
	}
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> k;
  	for (int i = 1;i <= n - 1;i++) {
  		int a, b;
  		cin >> a >> b;
  		g[a].push_back(b);
  		g[b].push_back(a);
  	}
  	for (int i = 1;i <= n;i++) {
  		cin >> a[i];
  		c[a[i]].push_back(i);
  	}
  	dfs(1, 0);
  	build(1, 0, 1);
 		int o = 0;
 		assert(cc[1]);
 		for (int i = 1;i <= n;i++) {
 			if (cc[i] && (int)t[i].size() == 1)
				o += 1;		
  	}
  	ans = (o + 1) / 2;
  	cout << ans << '\n';
  }
  return 0; 
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from mergers.cpp:1:
mergers.cpp: In function 'void dfs(long long int, long long int)':
mergers.cpp:33:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  assert(have[v] <= cnt[v].size());
      |         ~~~~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:34:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  if (have[v] == cnt[v].size())
      |      ~~~~~~~~^~~~~~~~~~~~~~~~

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