Submission #677152

#	Time	Username	Problem	Language	Result	Execution time	Memory
677152		Melika0gh	The Xana coup (BOI21_xanadu)	C++17	100 / 100	72 ms	19624 KiB

xanadu

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double   ld;
#define sync	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pb		push_back
#define pii		pair<int, int>
#define mp		make_pair
#define fi		first
#define se		second

const int maxn = 1e5 + 2, inf = 1e7;
vector<int> adj[maxn];
ll dp[maxn][2][2];
int sit[maxn];
int n;

void Dfs(int v, int p)
{
	for(int u : adj[v])
	{
		if(u != p)
			Dfs(u, v);
	}
	
	if(adj[v].size() == 1)
	{
		dp[v][sit[v]][0] = 0;
		dp[v][1 - sit[v]][1] = 1;
		return;
	}
	
	ll sum[2] = {0, 0}, w[2] = {inf, inf}, cnt[2] = {0, 0};
	for(int u : adj[v])
	{
		if(u == p)
			continue;
		
		sum[0] += min(dp[u][0][0], dp[u][0][1]);
		sum[1] += min(dp[u][1][0], dp[u][1][1]);
		w[0] = min(w[0], max(dp[u][0][0], dp[u][0][1]) - min(dp[u][0][0], dp[u][0][1]));
		w[1] = min(w[1], max(dp[u][1][0], dp[u][1][1]) - min(dp[u][1][0], dp[u][1][1]));
		
		cnt[0] += (dp[u][0][0] >= dp[u][0][1]);
		cnt[1] += (dp[u][1][0] >= dp[u][1][1]);
	}
	
	dp[v][sit[v]][0] = min(dp[v][sit[v]][0], sum[0] + (cnt[0] % 2 ? w[0] : 0));
	dp[v][1 - sit[v]][0] = min(dp[v][1 - sit[v]][0], sum[0] + (cnt[0] % 2 ? 0 : w[0]));
	dp[v][sit[v]][1] = min(dp[v][sit[v]][1], sum[1] + 1 + (cnt[1] % 2 ? 0 : w[1]));
	dp[v][1 - sit[v]][1] = min(dp[v][1-sit[v]][1], sum[1] + 1 + (cnt[1] % 2 ? w[1] : 0));
	
/*	cout << v << " : " << endl;
	cout << dp[v][0][0] << " , " << dp[v][0][1] << " , " << dp[v][1][0] << " , " << dp[v][1][1] << endl;
	cout << sum[0] << " + " << w[0] << " , " << sum[1] << " + " << w[1] << endl;*/
	return;
}

int main()
{
	sync;
	cin >> n;
	int r = 0;
	for(int i = 0; i < n-1; i++)
	{
		int v, u;
		cin >> v >> u;
		v--, u--;
		adj[v].pb(u);
		adj[u].pb(v);
		if(adj[v].size() > 1)
			r = v;
		if(adj[u].size() > 1)
			r = u;
	}
	for(int i = 0; i < n; i++)
		cin >> sit[i];
	
	for(int i = 0; i < n; i++)
		for(int j = 0; j < 2; j++)
			for(int k = 0; k < 2; k++)
				dp[i][j][k] = inf;
			
	//memset(dp, 63, sizeof dp);
	
	Dfs(r, -1);
	
	int ans = min(dp[r][0][0], dp[r][0][1]);
	if(ans > n)
		cout << "impossible" << '\n';
	else
		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