oj.uz

Submission #107425

# Submission time Handle Problem Language Result Execution time Memory
107425 2019-04-24T07:38:23 Z faceless Mergers (JOI19_mergers) C++14
0 / 100
 192 ms 77728 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], dp[maxn];
vector<int> t[maxn], vec[maxn];
bool pd[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;
		pd[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);
		psz[v] += vec[i].size();
	}
	DFS(nonleaf);
	bool flag = 0;
	for (int v = 1; v <= n; v++)
		if (par[v][0] != -1 and pd[v] == 0 and dp[v] == cnt and psz[v] == sz[v])
			flag = 1;
	cout << (cnt + 1) / 2 + flag << endl;
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 74240 KB Output is correct
2 Correct 192 ms 77728 KB Output is correct
3 Correct 61 ms 69116 KB Output is correct
4 Incorrect 58 ms 69112 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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