Submission #1123100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123100		NDT134	The Xana coup (BOI21_xanadu)	C++20	0 / 100	73 ms	8520 KiB

xanadu

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
using pi = pair<int, int>;
using pii = pair<pi, pi>;

int main() {
	int n; cin >> n;
	vector<vector<int>> g(n);
	for (int i = 0; i < n - 1; i++)
	{
		int a, b; cin >> a >> b; a--; b--;
		g[b].push_back(a); g[a].push_back(b);
	}
	vector<int> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}

	vector<int> p(n), ch(n);
	queue<int> q; q.push(0);
	while (!q.empty())
	{
		int x = q.front(); q.pop();
		for (int y : g[x])
		{
			if (p[x] != y)
			{
				p[y] = x;
				q.push(y);
				ch[x]++;
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		if (!ch[i])
		{
			q.push(i);
		}
	}

	vector<pii> dp(n);
	//vector<pi> dp2(n);
	int inf = n + 1;
	while (!q.empty())
	{
		int x = q.front(); q.pop();
		pi p1 = { 0, inf };
		pi p2 = { inf, 1 };
		if (v[x])
		{
			p1 = { inf, 0 };
			p2 = { 1, inf };
		}
		for (int y : g[x])
		{
			if (p[x] != y)
			{
				pi pp;

				pp.first = min(p1.first + dp[y].first.first,
					p1.second + dp[y].second.first);
				pp.second = min(p1.second + dp[y].first.first,
					p1.first + dp[y].second.first);
				p1 = pp;

				pp.first = min(p2.first + dp[y].first.second,
					p2.second + dp[y].second.second);
				pp.second = min(p2.second + dp[y].first.second,
					p2.first + dp[y].second.second);
				p2 = pp;
			}
		}
		dp[x] = { p1, p2 };

		ch[p[x]]--;
		if (!ch[p[x]])
		{
			q.push(p[x]);
		}
	}

	int r = min(dp[0].first.first, dp[0].second.first);
	if (r >= inf)
	{
		cout << "IMPOSSIBLE" << endl;
		return 0;
	}

	cout << r << endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30