Submission #677028

#	Time	Username	Problem	Language	Result	Execution time	Memory
677028		faribourz	The Xana coup (BOI21_xanadu)	C++14	100 / 100	84 ms	13580 KiB

xanadu

// Only GOD
// believe in yourself
// nemidam del be in darde donya!
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define bit(x, y) ((x >> y)&1)
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0

const int N = 1e5+10;
const int INF = 1e9;
int dp[N][4];
bool f[N];
vector<int> G[N];
void upd1(int v, int p){
	int cnt = 0;
	bool C = 0;
	for(int u : G[v]){
		if(u == p)
			continue;
		C |= (dp[u][0] >= INF && dp[u][2] >= INF);
		if(dp[u][0] < dp[u][2]){
			dp[v][0] += dp[u][0];
		}
		else{
			dp[v][0] += dp[u][2];
			cnt++;
		}
	}
	if(C){
		dp[v][0] = INF;
		dp[v][1] = INF;
		return;
	}
	dp[v][1] = dp[v][0];
	if((f[v] && cnt%2==0) || (!f[v] && cnt % 2)){
		int mn = INF;
		for(int u : G[v]){
			if(u==p)
				continue;
			if(dp[u][0] < INF && dp[u][2] < INF){
				mn = min(mn, abs(dp[u][0] - dp[u][2]));
			}
		}
		if(mn==INF){
			dp[v][0] = INF;
		}
		else{
			dp[v][0] += mn;
		}
	}
	else{
		int mn = INF;
		for(int u : G[v]){
			if(u==p)
				continue;
			if(dp[u][0] < INF && dp[u][2] < INF){
				mn = min(mn, abs(dp[u][0] - dp[u][2]));
			}
		}
		if(mn==INF){
			dp[v][1] = INF;
		}
		else{
			dp[v][1] += mn;
		}
	}
}
void upd2(int v, int p){
	int cnt = 0;
	bool C = 0;
	for(int u : G[v]){
		if(u == p)
			continue;
		C |= (dp[u][1] >= INF && dp[u][3] >= INF);
		if(dp[u][1] < dp[u][3]){
			dp[v][2] += dp[u][1];
		}
		else{
			dp[v][2] += dp[u][3];
			cnt++;
		}
	}
	if(C){
		dp[v][2] = INF;
		dp[v][3] = INF;
		return;
	}
	dp[v][2]++;
	dp[v][3] = dp[v][2];
	if((f[v] && cnt%2==0) || (!f[v] && cnt % 2)){
		int mn = INF;
		for(int u : G[v]){
			if(u==p)
				continue;
			if(dp[u][1] < INF && dp[u][3] < INF){
				mn = min(mn, abs(dp[u][1] - dp[u][3]));
			}
		}
		if(mn==INF){
			dp[v][3] = INF;
		}
		else{
			dp[v][3] += mn;
		}
	}
	else{
		int mn = INF;
		for(int u : G[v]){
			if(u==p)
				continue;
			if(dp[u][1] < INF && dp[u][3] < INF){
				mn = min(mn, abs(dp[u][1] - dp[u][3]));
			}
		}
		if(mn==INF){
			dp[v][2] = INF;
		}
		else{
			dp[v][2] += mn;
		}
	}
}
void DFS(int v, int p = -1){
	if(sz(G[v])==1 && p != -1){
		if(f[v]){
			dp[v][0] = INF, dp[v][1] = 0, dp[v][2] = 1, dp[v][3] = INF;
		}
		else{
			dp[v][0] = 0, dp[v][1] = INF, dp[v][2] = INF, dp[v][3] = 1;
		}
		return;
	}
	for(int u : G[v])if(u != p){
		DFS(u, v);
	}
	upd1(v, p);
	upd2(v, p);
}
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	for(int i =1;i < n ;i++){
		int v, u;
		cin >> v >> u ;
		G[v].pb(u);
		G[u].pb(v);
	}	
	for(int i = 1; i <= n; i++)
		cin >> f[i];
	DFS(1);
	int mn = min(dp[1][0], dp[1][2]);
	if(mn >= INF)
		KILL("impossible");
	KILL(mn);

}

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