oj.uz

Submission #377937

# Submission time Handle Problem Language Result Execution time Memory
377937 2021-03-15T15:08:28 Z casperwang Mergers (JOI19_mergers) C++14
0 / 100
 205 ms 70396 KB 
#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]);
		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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 51180 KB Output is correct
2 Incorrect 37 ms 51308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 51180 KB Output is correct
2 Incorrect 37 ms 51308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 51180 KB Output is correct
2 Incorrect 37 ms 51308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 61908 KB Output is correct
2 Incorrect 205 ms 70396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 51180 KB Output is correct
2 Incorrect 37 ms 51308 KB Output isn't correct
3 Halted 0 ms 0 KB -