제출 #933672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933672		beepbeepsheep	The Xana coup (BOI21_xanadu)	C++17	100 / 100	76 ms	51444 KiB

xanadu

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long, null_type, less_equal<>,
        rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
        
#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll inf=1e15;
const ll maxn=5e5+5;
const ll mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<ll> adj[maxn];
ll arr[maxn];
ll dp[maxn][2][2];
ll dfs(ll x, ll p, ll fs, ll fp){
	if (dp[x][fs][fp]!=-1) return dp[x][fs][fp];
	ll parity=arr[x]^fs^fp;
	dp[x][fs][fp]=fs;
	priority_queue<ll,vector<ll>,greater<ll>> pq;
	for (auto u:adj[x]){
		if (u==p) continue;
		dfs(u,x,0,fs);
		dfs(u,x,1,fs);
		dp[x][fs][fp]+=dp[u][0][fs];
		pq.emplace(dp[u][1][fs]-dp[u][0][fs]);
	}
	if (parity==1 && pq.empty()){
		return dp[x][fs][fp]=inf;
	}
	if (parity){
		dp[x][fs][fp]+=pq.top();
		pq.pop();
	}
	while (pq.size()){
		ll a=pq.top();
		pq.pop();
		if (pq.empty()) break;
		ll b=pq.top();
		pq.pop();
		if (a+b>=0) break;
		dp[x][fs][fp]+=(a+b); //add if we can get negative result
		//i.e. savings 
	}
	return dp[x][fs][fp];
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(dp,-1,sizeof(dp));
 	ll n,a,b;
 	cin>>n;
 	for (int i=1;i<n;i++){
 		cin>>a>>b;
 		adj[a].emplace_back(b);
 		adj[b].emplace_back(a);
 	}
 	for (int i=1;i<=n;i++) cin>>arr[i];
 	dfs(1,0,0,0);
 	dfs(1,0,1,0);
 	ll ans=min(dp[1][0][0],dp[1][1][0]);
 	if (ans>=inf){
 		cout<<"impossible";
 	} else cout<<ans;
	return 0;
}

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