oj.uz

답안 #987074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
987074 2024-05-21T19:26:23 Z OAleksa Mergers (JOI19_mergers) C++14
0 / 100
 3000 ms 89324 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];
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);
		x = v;
	}
	for (auto u : g[v]) {
		if (u == p)
			continue;
		build(u, v, x);
	}
}
void calc(int v, int p) {
	for (auto u : t[v]) {
		if (u == p)
			continue;
		dep[u] = dep[v] + 1;
		calc(u, v);
	}
}
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);
 		int o = 0;
 		for (int i = 1;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 = 1;i <= n;i++) {
 				if (cnt[i] && t[i].size() == 1)
 					mn = min(mn, dep[i]);
 			}
 			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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 41308 KB Output is correct
2 Correct 15 ms 41304 KB Output is correct
3 Correct 15 ms 41560 KB Output is correct
4 Correct 12 ms 41496 KB Output is correct
5 Correct 13 ms 41308 KB Output is correct
6 Correct 13 ms 41304 KB Output is correct
7 Correct 13 ms 41308 KB Output is correct
8 Correct 9 ms 41460 KB Output is correct
9 Correct 15 ms 41308 KB Output is correct
10 Correct 13 ms 41392 KB Output is correct
11 Correct 11 ms 41308 KB Output is correct
12 Correct 9 ms 41560 KB Output is correct
13 Correct 14 ms 41304 KB Output is correct
14 Correct 13 ms 41304 KB Output is correct
15 Correct 14 ms 41308 KB Output is correct
16 Incorrect 13 ms 41304 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 41308 KB Output is correct
2 Correct 15 ms 41304 KB Output is correct
3 Correct 15 ms 41560 KB Output is correct
4 Correct 12 ms 41496 KB Output is correct
5 Correct 13 ms 41308 KB Output is correct
6 Correct 13 ms 41304 KB Output is correct
7 Correct 13 ms 41308 KB Output is correct
8 Correct 9 ms 41460 KB Output is correct
9 Correct 15 ms 41308 KB Output is correct
10 Correct 13 ms 41392 KB Output is correct
11 Correct 11 ms 41308 KB Output is correct
12 Correct 9 ms 41560 KB Output is correct
13 Correct 14 ms 41304 KB Output is correct
14 Correct 13 ms 41304 KB Output is correct
15 Correct 14 ms 41308 KB Output is correct
16 Incorrect 13 ms 41304 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 41308 KB Output is correct
2 Correct 15 ms 41304 KB Output is correct
3 Correct 15 ms 41560 KB Output is correct
4 Correct 12 ms 41496 KB Output is correct
5 Correct 13 ms 41308 KB Output is correct
6 Correct 13 ms 41304 KB Output is correct
7 Correct 13 ms 41308 KB Output is correct
8 Correct 9 ms 41460 KB Output is correct
9 Correct 15 ms 41308 KB Output is correct
10 Correct 13 ms 41392 KB Output is correct
11 Correct 11 ms 41308 KB Output is correct
12 Correct 9 ms 41560 KB Output is correct
13 Correct 14 ms 41304 KB Output is correct
14 Correct 13 ms 41304 KB Output is correct
15 Correct 14 ms 41308 KB Output is correct
16 Incorrect 13 ms 41304 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 88980 KB Output is correct
2 Execution timed out 3058 ms 89324 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 41308 KB Output is correct
2 Correct 15 ms 41304 KB Output is correct
3 Correct 15 ms 41560 KB Output is correct
4 Correct 12 ms 41496 KB Output is correct
5 Correct 13 ms 41308 KB Output is correct
6 Correct 13 ms 41304 KB Output is correct
7 Correct 13 ms 41308 KB Output is correct
8 Correct 9 ms 41460 KB Output is correct
9 Correct 15 ms 41308 KB Output is correct
10 Correct 13 ms 41392 KB Output is correct
11 Correct 11 ms 41308 KB Output is correct
12 Correct 9 ms 41560 KB Output is correct
13 Correct 14 ms 41304 KB Output is correct
14 Correct 13 ms 41304 KB Output is correct
15 Correct 14 ms 41308 KB Output is correct
16 Incorrect 13 ms 41304 KB Output isn't correct
17 Halted 0 ms 0 KB -