oj.uz

Submission #107421

# Submission time Handle Problem Language Result Execution time Memory
107421 2019-04-24T07:28:30 Z faceless Mergers (JOI19_mergers) C++14
10 / 100
 238 ms 79000 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 10;
const int maxl = 21;
int cnt, par[maxn][maxl + 2], h[maxn], s[maxn], sz[maxn], psz[maxn];
bool dp[maxn];
vector<int> t[maxn], vec[maxn];

void DFS(int v){
	sz[v] = 1;
	for (auto u : t[v]){
		if (u != par[v][0]){
			DFS(u);
			sz[v] += sz[u];
			psz[v] += psz[u];
			dp[v] |= dp[u];
		}
	}
	if (dp[v] == 0 and sz[v] == psz[v] and par[v][0] != -1){
		cnt ++;
		dp[v] = 1;
	}
}

int lca(int v, int u){
	if (h[v] < h[u])
		swap(v, u);
//	cout << "LCA " << v << " " << u << " -> ";
	for (int i = maxl - 1; i >= 0; i--)
		if (h[v] - (1 << i) >= h[u])
			v = par[v][i];
//	cout << v << endl;
	if (v == u)
		return v;
	for (int i = maxl - 1; i >= 0; i--){
		if (par[v][i] != par[u][i]){
			v = par[v][i];
			u = par[u][i];
		}
	}
	return par[v][0];
}

void dfs(int v, int p = -1){
	par[v][0] = p;
	for (int i = 1; i < maxl and par[v][i - 1] != -1; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	for (auto u : t[v]){
		if (u != p){
			h[u] = h[v] + 1;
			dfs(u, v);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n - 1; i++){
		int v, u;
		cin >> v >> u;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	int nonleaf = -1;
	for (int v = 1; v <= n; v++)
		if (t[v].size() > 1)
			nonleaf = v;
	memset(par, -1, sizeof par);
	dfs(nonleaf);

	for (int v = 1; v <= n; v++){
		cin >> s[v];
		vec[s[v]].push_back(v);
	}
	for (int i = 1; i <= k; i++){
		int v = vec[i][0];
		for (auto u : vec[i])
			v = lca(v, u);
//		cout << "# " << k << " -> " << v << endl;
		psz[v] += vec[i].size();
	}
	DFS(nonleaf);
	cout << (cnt + 1) / 2 << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 68856 KB Output is correct
2 Correct 63 ms 68860 KB Output is correct
3 Correct 63 ms 68856 KB Output is correct
4 Correct 60 ms 68856 KB Output is correct
5 Correct 60 ms 68856 KB Output is correct
6 Correct 61 ms 68984 KB Output is correct
7 Correct 60 ms 68856 KB Output is correct
8 Correct 59 ms 68856 KB Output is correct
9 Correct 64 ms 68828 KB Output is correct
10 Correct 62 ms 68828 KB Output is correct
11 Correct 64 ms 68856 KB Output is correct
12 Correct 63 ms 68984 KB Output is correct
13 Correct 62 ms 68856 KB Output is correct
14 Correct 60 ms 68856 KB Output is correct
15 Correct 58 ms 68856 KB Output is correct
16 Correct 58 ms 68856 KB Output is correct
17 Correct 64 ms 68856 KB Output is correct
18 Correct 60 ms 68856 KB Output is correct
19 Correct 58 ms 68856 KB Output is correct
20 Correct 58 ms 68856 KB Output is correct
21 Correct 57 ms 68856 KB Output is correct
22 Correct 60 ms 68856 KB Output is correct
23 Correct 65 ms 68856 KB Output is correct
24 Correct 61 ms 68856 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 68856 KB Output is correct
2 Correct 63 ms 68860 KB Output is correct
3 Correct 63 ms 68856 KB Output is correct
4 Correct 60 ms 68856 KB Output is correct
5 Correct 60 ms 68856 KB Output is correct
6 Correct 61 ms 68984 KB Output is correct
7 Correct 60 ms 68856 KB Output is correct
8 Correct 59 ms 68856 KB Output is correct
9 Correct 64 ms 68828 KB Output is correct
10 Correct 62 ms 68828 KB Output is correct
11 Correct 64 ms 68856 KB Output is correct
12 Correct 63 ms 68984 KB Output is correct
13 Correct 62 ms 68856 KB Output is correct
14 Correct 60 ms 68856 KB Output is correct
15 Correct 58 ms 68856 KB Output is correct
16 Correct 58 ms 68856 KB Output is correct
17 Correct 64 ms 68856 KB Output is correct
18 Correct 60 ms 68856 KB Output is correct
19 Correct 58 ms 68856 KB Output is correct
20 Correct 58 ms 68856 KB Output is correct
21 Correct 57 ms 68856 KB Output is correct
22 Correct 60 ms 68856 KB Output is correct
23 Correct 65 ms 68856 KB Output is correct
24 Correct 61 ms 68856 KB Output is correct
25 Correct 59 ms 68856 KB Output is correct
26 Correct 65 ms 69112 KB Output is correct
27 Correct 65 ms 68984 KB Output is correct
28 Correct 64 ms 69124 KB Output is correct
29 Correct 61 ms 69112 KB Output is correct
30 Correct 60 ms 69112 KB Output is correct
31 Correct 60 ms 68856 KB Output is correct
32 Correct 63 ms 69240 KB Output is correct
33 Correct 58 ms 68876 KB Output is correct
34 Correct 62 ms 69112 KB Output is correct
35 Correct 68 ms 69240 KB Output is correct
36 Incorrect 60 ms 69112 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 68856 KB Output is correct
2 Correct 63 ms 68860 KB Output is correct
3 Correct 63 ms 68856 KB Output is correct
4 Correct 60 ms 68856 KB Output is correct
5 Correct 60 ms 68856 KB Output is correct
6 Correct 61 ms 68984 KB Output is correct
7 Correct 60 ms 68856 KB Output is correct
8 Correct 59 ms 68856 KB Output is correct
9 Correct 64 ms 68828 KB Output is correct
10 Correct 62 ms 68828 KB Output is correct
11 Correct 64 ms 68856 KB Output is correct
12 Correct 63 ms 68984 KB Output is correct
13 Correct 62 ms 68856 KB Output is correct
14 Correct 60 ms 68856 KB Output is correct
15 Correct 58 ms 68856 KB Output is correct
16 Correct 58 ms 68856 KB Output is correct
17 Correct 64 ms 68856 KB Output is correct
18 Correct 60 ms 68856 KB Output is correct
19 Correct 58 ms 68856 KB Output is correct
20 Correct 58 ms 68856 KB Output is correct
21 Correct 57 ms 68856 KB Output is correct
22 Correct 60 ms 68856 KB Output is correct
23 Correct 65 ms 68856 KB Output is correct
24 Correct 61 ms 68856 KB Output is correct
25 Correct 62 ms 68828 KB Output is correct
26 Correct 145 ms 75628 KB Output is correct
27 Correct 200 ms 75728 KB Output is correct
28 Correct 70 ms 69084 KB Output is correct
29 Correct 66 ms 68848 KB Output is correct
30 Correct 59 ms 68860 KB Output is correct
31 Incorrect 213 ms 75640 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 75596 KB Output is correct
2 Correct 175 ms 79000 KB Output is correct
3 Correct 67 ms 69112 KB Output is correct
4 Correct 65 ms 69112 KB Output is correct
5 Correct 67 ms 68856 KB Output is correct
6 Correct 63 ms 68904 KB Output is correct
7 Correct 65 ms 69056 KB Output is correct
8 Correct 238 ms 77156 KB Output is correct
9 Incorrect 70 ms 69112 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 68856 KB Output is correct
2 Correct 63 ms 68860 KB Output is correct
3 Correct 63 ms 68856 KB Output is correct
4 Correct 60 ms 68856 KB Output is correct
5 Correct 60 ms 68856 KB Output is correct
6 Correct 61 ms 68984 KB Output is correct
7 Correct 60 ms 68856 KB Output is correct
8 Correct 59 ms 68856 KB Output is correct
9 Correct 64 ms 68828 KB Output is correct
10 Correct 62 ms 68828 KB Output is correct
11 Correct 64 ms 68856 KB Output is correct
12 Correct 63 ms 68984 KB Output is correct
13 Correct 62 ms 68856 KB Output is correct
14 Correct 60 ms 68856 KB Output is correct
15 Correct 58 ms 68856 KB Output is correct
16 Correct 58 ms 68856 KB Output is correct
17 Correct 64 ms 68856 KB Output is correct
18 Correct 60 ms 68856 KB Output is correct
19 Correct 58 ms 68856 KB Output is correct
20 Correct 58 ms 68856 KB Output is correct
21 Correct 57 ms 68856 KB Output is correct
22 Correct 60 ms 68856 KB Output is correct
23 Correct 65 ms 68856 KB Output is correct
24 Correct 61 ms 68856 KB Output is correct
25 Correct 59 ms 68856 KB Output is correct
26 Correct 65 ms 69112 KB Output is correct
27 Correct 65 ms 68984 KB Output is correct
28 Correct 64 ms 69124 KB Output is correct
29 Correct 61 ms 69112 KB Output is correct
30 Correct 60 ms 69112 KB Output is correct
31 Correct 60 ms 68856 KB Output is correct
32 Correct 63 ms 69240 KB Output is correct
33 Correct 58 ms 68876 KB Output is correct
34 Correct 62 ms 69112 KB Output is correct
35 Correct 68 ms 69240 KB Output is correct
36 Incorrect 60 ms 69112 KB Output isn't correct
37 Halted 0 ms 0 KB -