Submission #787811

#	Time	Username	Problem	Language	Result	Execution time	Memory
787811		ByeWorld	The Xana coup (BOI21_xanadu)	C++14	100 / 100	79 ms	33016 KiB

xanadu

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
#define int long long 
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
using namespace std;
const int MAXN = 1e5+10;
const int SQRT = 700;
const int MOD = 998244353;
const int LOG = 21;
const int INF = 1e13+10;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;

int n;
vector <int> adj[MAXN];
int dp[MAXN][2][2];
int b[MAXN];

void dfs(int nw, int par){
	if(par!=-1 && adj[nw].size() == 1){
		if(b[nw]){
			dp[nw][0][1] = 0;
			dp[nw][1][0] = 1;
			dp[nw][1][1] = INF;
			dp[nw][0][0] = INF;
		} else {
			dp[nw][0][0] = 0;
			dp[nw][1][1] = 1;
			dp[nw][1][0] = INF;
			dp[nw][0][1] = INF;
		}
		return;
	}

	vector <int> vec[2][2];
	for(auto nx : adj[nw]){
		if(nx == par) continue;
		dfs(nx, nw); //build dp bawah
	}

	//klik 1, nyala 1
	for(auto nx : adj[nw]){
		if(nx == par) continue;
		dp[nw][1][1] += dp[nx][0][1];
		vec[1][1].pb(dp[nx][1][1]-dp[nx][0][1]); //switch gk klik nyala -> klik nyala
	}
	sort(vec[1][1].begin(), vec[1][1].end());
	int sum = 0, mx = 0, mx2 = 0, cnt = 0;
	for(int i=0; i<vec[1][1].size(); i++){
		int in = vec[1][1][i];
		if(cnt==0){
			sum += in; mx2 = mx; mx = in; cnt++; continue;
		}
		sum += in; mx2 = mx; mx = in; cnt++;
		if(in > 0) break;
	}
	int te = sum;
	if(vec[1][1].size()>=2) te = min(sum, sum-mx-mx2);
	if(b[nw] == 1){ //odd->odd klik nyala, optimal
		if(cnt%2==1) dp[nw][1][1] += te;
		else dp[nw][1][1] += (sum-mx);
	} else {
		if(cnt%2==1) dp[nw][1][1] += (sum-mx);
		else dp[nw][1][1] += te;
	}
	dp[nw][1][1]++;


	//klik 1, nyala 0
	for(auto nx : adj[nw]){
		if(nx == par) continue;
		dp[nw][1][0] += dp[nx][0][1];
		vec[1][0].pb(dp[nx][1][1]-dp[nx][0][1]); //switch gk klik nyala -> klik nyala
	}
	sort(vec[1][0].begin(), vec[1][0].end());
	sum = 0, mx = 0, cnt = 0;
	for(int i=0; i<vec[1][0].size(); i++){
		int in = vec[1][0][i];
		if(cnt==0){
			sum += in; mx2 = mx; mx = in; cnt++; continue;
		}
		sum += in; mx2 = mx; mx = in; cnt++;
		if(in > 0) break;
	}
	te = sum;
	if(vec[1][0].size()>=2) te = min(sum, sum-mx-mx2);
	if(b[nw] == 1){ //odd->even klik nyala
		if(cnt%2==1) dp[nw][1][0] += (sum-mx);
		else dp[nw][1][0] += te;
	} else {
		if(cnt%2==1) dp[nw][1][0] += te;
		else dp[nw][1][0] += (sum-mx);
	}
	dp[nw][1][0]++;

	//klik 0, nyala 0
	for(auto nx : adj[nw]){
		if(nx == par) continue;
		dp[nw][0][0] += dp[nx][0][0];
		vec[0][0].pb(dp[nx][1][0]-dp[nx][0][0]); //switch gk klik mati -> klik mati
	}
	sort(vec[0][0].begin(), vec[0][0].end());
	sum = 0, mx = 0, cnt = 0;
	for(int i=0; i<vec[0][0].size(); i++){
		int in = vec[0][0][i];
		if(cnt==0){
			sum += in; mx2 = mx; mx = in; cnt++; continue;
		}
		sum += in; mx2 = mx; mx = in; cnt++;
		if(in>0) break;
	}
	te = sum;
	if(vec[0][0].size()>=2) te = min(sum, sum-mx-mx2);
	if(b[nw] == 1){ //odd->odd klik nyala
		if(cnt%2==1) dp[nw][0][0] += te;
		else dp[nw][0][0] += (sum-mx);
	} else {
		if(cnt%2==1) dp[nw][0][0] += (sum-mx);
		else dp[nw][0][0] += te;
	}

	//klik 0, nyala 1
	for(auto nx : adj[nw]){
		if(nx == par) continue;
		dp[nw][0][1] += dp[nx][0][0];
		vec[0][1].pb(dp[nx][1][0]-dp[nx][0][0]); //switch gk klik mati -> klik mati
	}
	sort(vec[0][1].begin(), vec[0][1].end());
	sum = 0, mx = 0, cnt = 0;
	for(int i=0; i<vec[0][1].size(); i++){
		int in = vec[0][1][i];
		if(cnt==0){
			sum += in; mx2 = mx; mx = in; cnt++; continue;
		}
		sum += in; mx2 = mx; mx = in; cnt++;
		if(in>0) break;
	}
	te = sum;
	if(vec[0][1].size()>=2) te = min(sum, sum-mx-mx2);
	if(b[nw] == 1){ //odd->even klik nyala
		if(cnt%2==1) dp[nw][0][1] += (sum-mx);
		else dp[nw][0][1] += te;
	} else {
		if(cnt%2==1) dp[nw][0][1] += te;
		else dp[nw][0][1] += (sum-mx);
	}
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i=1; i<=n-1; i++){
		int x, y; cin >> x >> y;
		adj[x].pb(y); adj[y].pb(x);
	}
	for(int i=1; i<=n; i++) cin >> b[i];
	dfs(1, -1);
	int ans = min(dp[1][1][0], dp[1][0][0]);
	if(ans>=n) cout << "impossible\n";
	else cout << ans << '\n';
	// for(int i=1; i<=n; i++){
	// 	cout << i << ' '<< dp[i][1][1] << ' ' << dp[i][1][0] << ' ' << dp[i][0][1] << ' ' << dp[i][0][0] << '\n';
	// }
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:52:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0; i<vec[1][1].size(); i++){
      |               ~^~~~~~~~~~~~~~~~~
xanadu.cpp:80:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i=0; i<vec[1][0].size(); i++){
      |               ~^~~~~~~~~~~~~~~~~
xanadu.cpp:107:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for(int i=0; i<vec[0][0].size(); i++){
      |               ~^~~~~~~~~~~~~~~~~
xanadu.cpp:133:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |  for(int i=0; i<vec[0][1].size(); i++){
      |               ~^~~~~~~~~~~~~~~~~

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