제출 #677148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677148		Melika0gh	The Xana coup (BOI21_xanadu)	C++17	30 / 100	64 ms	16792 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];
int 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;
	}
	
	int 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][0][0] = sum[0];
	dp[v][1][0] = sum[0];
	dp[v][0][1] = sum[1] + 1;
	dp[v][1][1] = sum[1] + 1;
	
	if(sit[v] == 1)
	{
		if(cnt[0] % 2)
			dp[v][1][0] += w[0];
		else
			dp[v][0][0] += w[0];
		
		if(cnt[1] % 2)
			dp[v][0][1] += w[1];
		else
			dp[v][1][1] += w[1];
	}
	else
	{
		if(cnt[0] % 2)
			dp[v][0][0] += w[0];
		else
			dp[v][1][0] += w[0];
		
		if(cnt[1] % 2)
			dp[v][1][1] += w[1];
		else
			dp[v][0][1] += w[1];
	}
	
/*	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: 0 / 40
• Subtask 5: 0 / 30