제출 #472194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472194		prvocislo	Mergers (JOI19_mergers)	C++17	100 / 100	883 ms	75404 KiB

mergers

#include <iostream>
#include <vector>
using namespace std;

const int maxn = 5e5 + 5;
int n, k, t = 0;
int l[maxn], r[maxn];
int ls[maxn], rs[maxn], s[maxn];
int l2[maxn], r2[maxn];
vector<int> g[maxn];
bool c[maxn];
void dfs_time(int u, int p = -1)
{
	l[u] = t++;
	for (int v : g[u]) if (v != p) dfs_time(v, u);
	r[u] = t - 1;
}
void dfs_critical(int u, int p = -1)
{
	l2[u] = min(l[u], ls[s[u]]);
	r2[u] = max(r[u], rs[s[u]]);
	for (int v : g[u]) if (v != p)
	{
		dfs_critical(v, u);
		l2[u] = min(l2[u], l2[v]);
		r2[u] = max(r2[u], r2[v]);
	}
	if (u && l[u] == l2[u] && r[u] == r2[u])
		c[u] = true;
}
int cuts = 0;
bool dfs_cover(int u, int p = -1)
{
	bool is_covered = false;
	for (int v : g[u]) if (v != p) is_covered |= dfs_cover(v, u);
	if (!is_covered && c[u])
	{
		cuts++;
		return true;
	}
	return is_covered;
}
int dfs_cuts_root_can_reach(int u, int p = -1)
{
	if (c[u]) return 1;
	int sum = 0;
	for (int v : g[u]) if (v != p) sum += dfs_cuts_root_can_reach(v, u);
	return sum;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 0, a, b; i < n - 1; i++)
	{
		cin >> a >> b;
		g[--a].push_back(--b);
		g[b].push_back(a);
	}
	dfs_time(0);
	for (int i = 0; i < k; i++) ls[i] = 1e9, rs[i] = -1e9;
	for (int i = 0; i < n; i++)
	{
		cin >> s[i]; s[i]--;
		ls[s[i]] = min(ls[s[i]], l[i]);
		rs[s[i]] = max(rs[s[i]], r[i]);
	}
	dfs_critical(0);
	dfs_cover(0);
	int ans = (cuts + 1) / 2;
	int cnt = dfs_cuts_root_can_reach(0);
	if (cuts % 2 == 0 && cnt == 1) ans++; // musime to este spojit aj s korenom
	cout << ans << "\n";
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30