oj.uz

Submission #377938

# Submission time Handle Problem Language Result Execution time Memory
377938 2021-03-15T15:10:33 Z casperwang Mergers (JOI19_mergers) C++14
0 / 100
 186 ms 70232 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]);
		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

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.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 51180 KB Output is correct
2 Correct 36 ms 51308 KB Output is correct
3 Correct 35 ms 51308 KB Output is correct
4 Correct 35 ms 51308 KB Output is correct
5 Correct 35 ms 51308 KB Output is correct
6 Correct 35 ms 51308 KB Output is correct
7 Correct 35 ms 51308 KB Output is correct
8 Correct 40 ms 51328 KB Output is correct
9 Correct 35 ms 51308 KB Output is correct
10 Correct 35 ms 51320 KB Output is correct
11 Correct 36 ms 51328 KB Output is correct
12 Correct 35 ms 51308 KB Output is correct
13 Correct 36 ms 51308 KB Output is correct
14 Correct 36 ms 51308 KB Output is correct
15 Correct 36 ms 51308 KB Output is correct
16 Incorrect 35 ms 51308 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 51180 KB Output is correct
2 Correct 36 ms 51308 KB Output is correct
3 Correct 35 ms 51308 KB Output is correct
4 Correct 35 ms 51308 KB Output is correct
5 Correct 35 ms 51308 KB Output is correct
6 Correct 35 ms 51308 KB Output is correct
7 Correct 35 ms 51308 KB Output is correct
8 Correct 40 ms 51328 KB Output is correct
9 Correct 35 ms 51308 KB Output is correct
10 Correct 35 ms 51320 KB Output is correct
11 Correct 36 ms 51328 KB Output is correct
12 Correct 35 ms 51308 KB Output is correct
13 Correct 36 ms 51308 KB Output is correct
14 Correct 36 ms 51308 KB Output is correct
15 Correct 36 ms 51308 KB Output is correct
16 Incorrect 35 ms 51308 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 51180 KB Output is correct
2 Correct 36 ms 51308 KB Output is correct
3 Correct 35 ms 51308 KB Output is correct
4 Correct 35 ms 51308 KB Output is correct
5 Correct 35 ms 51308 KB Output is correct
6 Correct 35 ms 51308 KB Output is correct
7 Correct 35 ms 51308 KB Output is correct
8 Correct 40 ms 51328 KB Output is correct
9 Correct 35 ms 51308 KB Output is correct
10 Correct 35 ms 51320 KB Output is correct
11 Correct 36 ms 51328 KB Output is correct
12 Correct 35 ms 51308 KB Output is correct
13 Correct 36 ms 51308 KB Output is correct
14 Correct 36 ms 51308 KB Output is correct
15 Correct 36 ms 51308 KB Output is correct
16 Incorrect 35 ms 51308 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 61796 KB Output is correct
2 Incorrect 186 ms 70232 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 51180 KB Output is correct
2 Correct 36 ms 51308 KB Output is correct
3 Correct 35 ms 51308 KB Output is correct
4 Correct 35 ms 51308 KB Output is correct
5 Correct 35 ms 51308 KB Output is correct
6 Correct 35 ms 51308 KB Output is correct
7 Correct 35 ms 51308 KB Output is correct
8 Correct 40 ms 51328 KB Output is correct
9 Correct 35 ms 51308 KB Output is correct
10 Correct 35 ms 51320 KB Output is correct
11 Correct 36 ms 51328 KB Output is correct
12 Correct 35 ms 51308 KB Output is correct
13 Correct 36 ms 51308 KB Output is correct
14 Correct 36 ms 51308 KB Output is correct
15 Correct 36 ms 51308 KB Output is correct
16 Incorrect 35 ms 51308 KB Output isn't correct
17 Halted 0 ms 0 KB -