oj.uz

Submission #987077

# Submission time Handle Problem Language Result Execution time Memory
987077 2024-05-21T19:45:11 Z OAleksa Mergers (JOI19_mergers) C++14
0 / 100
 3000 ms 89908 KB 
#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, cnt[N], dep[N], up[N], is[N];
vector<int> g[N], c[N];
vector<int> t[N];
int have[N][52];
void dfs(int v, int p) {
	have[v][a[v]] = 1;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
		for (int j = 1;j <= k;j++)
			have[v][j] += have[u][j];
	}
	int ok = 1;
	for (int j = 1;j <= k;j++) {
		if (have[v][j] > 0)
			ok &= (have[v][j] == c[j].size());
	}
	cnt[v] = ok;
}
void build(int v, int p, int c) {
	int x = c;
	if (cnt[v] && v > 1) {
		t[v].push_back(c);
		t[c].push_back(v);
		up[v] = c;
		x = v;
	}
	for (auto u : g[v]) {
		if (u == p)
			continue;
		build(u, v, x);
	}
}
void calc(int v, int p) {
	if (t[v].size() == 1 && v > 1)
		is[v] = 1;
	for (auto u : t[v]) {
		if (u == p)
			continue;
		calc(u, v);
		is[v] += is[u];
	}
}
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);
  	calc(1, 0);
  	assert(cnt[1] == 1);
 		int o = 0;
 		for (int i = 2;i <= n;i++) {
 			if (cnt[i] && t[i].size() == 1)
				o += 1;		
  	}
 		if (o % 2 == 0)
 			ans = o / 2;
 		else {
 			int mn = 1e9;
 			for (int i = 2;i <= n;i++) {
 				if (cnt[i] && t[i].size() == 1) {
 					int t = i, s = 0;
 					while (t != 1) {
 						s += (is[t] == 1);
 						t = up[t];
 					}
 					mn = min(mn, s);
 				}
 			}
 			ans = o / 2 + mn;
 		}
  	cout << ans << '\n';
  }
  return 0; 
}

Compilation message

mergers.cpp: In function 'void dfs(long long int, long long int)':
mergers.cpp:24:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |    ok &= (have[v][j] == c[j].size());
      |           ~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43356 KB Output is correct
2 Correct 13 ms 43356 KB Output is correct
3 Incorrect 13 ms 43356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43356 KB Output is correct
2 Correct 13 ms 43356 KB Output is correct
3 Incorrect 13 ms 43356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43356 KB Output is correct
2 Correct 13 ms 43356 KB Output is correct
3 Incorrect 13 ms 43356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 89028 KB Output is correct
2 Execution timed out 3009 ms 89908 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43356 KB Output is correct
2 Correct 13 ms 43356 KB Output is correct
3 Incorrect 13 ms 43356 KB Output isn't correct
4 Halted 0 ms 0 KB -