Submission #872345

#	Time	Username	Problem	Language	Result	Execution time	Memory
872345		Cyber_Wolf	The Xana coup (BOI21_xanadu)	C++17	100 / 100	118 ms	45676 KiB

xanadu

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg N = 1e5+5;

vector<lg> adj[N];
lg c[N];
lg dp[N][2][2];
lg n;

lg dfs(lg src, lg ef, lg cur, lg par = - 1)
{
	auto&ret = dp[src][ef][cur];
	if(~ret)	return ret;
	ret = n+2;
	lg sz = adj[src].size();
	vector<vector<lg>> dp2(sz+1, vector<lg> (2, n+2));
	dp2[0][0] = 0;
	for(int i = 1; i <= sz; i++)
	{
		if(adj[src][i-1] == par)
		{
			dp2[i][0] = dp2[i-1][0];
			dp2[i][1] = dp2[i-1][1];
			continue;
		}
		dp2[i][0] = min(dp2[i-1][0]+dfs(adj[src][i-1], 0, ef^c[adj[src][i-1]], src), dp2[i-1][1]+dfs(adj[src][i-1], 1, ef^1^c[adj[src][i-1]], src)+1);
		dp2[i][1] = min(dp2[i-1][1]+dfs(adj[src][i-1], 0, ef^c[adj[src][i-1]], src), dp2[i-1][0]+dfs(adj[src][i-1], 1, ef^1^c[adj[src][i-1]], src)+1);
	}
	ret = dp2[sz][cur];
	return ret;
}

int main()
{
	fastio;
	cin >> n;
	for(int i = 1; i < n; i++)
	{
		lg u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 1; i <= n; i++)	cin >> c[i];
	memset(dp, -1, sizeof(dp));
	lg ans = min(dfs(1, 0, c[1]), dfs(1, 1, c[1]^1)+1);
	if(ans > n)
	{
		cout << "impossible\n";
		return 0;
	}
	cout << ans << '\n';

    return 0;
}

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