Submission #826555

#	Time	Username	Problem	Language	Result	Execution time	Memory
826555		aaron_dcoder	The Xana coup (BOI21_xanadu)	C++17	100 / 100	104 ms	12684 KiB

xanadu

#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr
#define dbgv(VARN) ((void)0)
#define dbg_for if constexpr (false) for
#else 
#pragma GCC optimize("trapv")
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#define dbg_for for
#define dbg(TXTMSG) cerr << "\n" << (TXTMSG)
#define dbgv(VARN) cerr << "\n" << (#VARN) << " = "<< (VARN) << ", line: " << __LINE__ << "\n"
#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
constexpr ll INFTY = 1e10;
#define var const auto&
/*
node_black_untoggled, node_black_toggled;
node_white_untoggled, node_white_toggled;
*/
using dp_state = array<array<ll,2>,2> ;

int main() {
	ll N;
	cin >> N;
	vector<vector<ll>> cam_connexion(N,vector<ll>());

	for (int i = 0; i < (N-1); ++i)
	{
		ll ai,bi;
		cin >> ai >> bi;
		ai--;bi--; //c

		cam_connexion[ai].push_back(bi);
		cam_connexion[bi].push_back(ai);
	}

	//0-off 1-on
	vector<ll> initial_state(N,-1);

	for (int i = 0; i < N; ++i)
	{
		cin >> initial_state[i];
	}

// >=INFTY signifies impossiblity
#define UN_PROCESSED dp_state{array<ll,2>{-1,-1},array<ll,2>{-1,-1}}
#define BEING_PROCESSED dp_state{array<ll,2>{-2,-2},array<ll,2>{-2,-2}}
	vector<dp_state> subtree_bests(N,UN_PROCESSED);

//cam-0 taken as root
	stack<ll> dfs({0});

	while (!dfs.empty()) {
		ll curr_node = dfs.top();

		if (subtree_bests[curr_node]==UN_PROCESSED) {
			for (var relative : cam_connexion[curr_node])
			{
				if (subtree_bests[relative]!=BEING_PROCESSED) {
					assert(subtree_bests[relative]==UN_PROCESSED);
					dfs.push(relative);
				}
			}
			subtree_bests[curr_node]=BEING_PROCESSED;
		}
		else if (subtree_bests[curr_node]==BEING_PROCESSED) {
			if (cam_connexion[curr_node].size()==1 && curr_node!=0) {
				if (initial_state[curr_node]==0) {
					subtree_bests[curr_node]=dp_state{array<ll,2>{0,INFTY},array<ll,2>{INFTY,1}};
				}
				else {
					subtree_bests[curr_node]=dp_state{array<ll,2>{INFTY,1},array<ll,2>{0,INFTY}};	
				}
				dfs.pop();
				continue;
			}
			
			for (ll toggled = 0; toggled <=1; toggled++)
			{
				ll res_toggle_of_best = 0;
				ll bestcost = toggled;
				ll leastdiff = INFTY;
				for (var relative : cam_connexion[curr_node])
				{
					if (subtree_bests[relative]!=BEING_PROCESSED) {
						assert(subtree_bests[relative]!=UN_PROCESSED);
						if (subtree_bests[relative][toggled][0]==INFTY && subtree_bests[relative][toggled][1]==INFTY) {
							subtree_bests[curr_node][0][toggled] = INFTY;
							subtree_bests[curr_node][1][toggled] = INFTY;
							goto caseToggled;
						}
						bestcost+=min(subtree_bests[relative][toggled][0],subtree_bests[relative][toggled][1]);
						res_toggle_of_best ^= subtree_bests[relative][toggled][1]<subtree_bests[relative][toggled][0];

						if (subtree_bests[relative][toggled][0]!= INFTY && subtree_bests[relative][toggled][1]!=INFTY) {
							leastdiff = min(leastdiff,abs(subtree_bests[relative][toggled][1]-subtree_bests[relative][toggled][0]));
						}
					}
				}
				dbgv(curr_node);dbgv(toggled);dbgv(res_toggle_of_best);dbgv(bestcost);dbgv(leastdiff);
				dbgv((res_toggle_of_best^initial_state[curr_node]^toggled));
				subtree_bests[curr_node][res_toggle_of_best^initial_state[curr_node]^toggled][toggled] = bestcost;
				subtree_bests[curr_node][res_toggle_of_best^initial_state[curr_node]^1^toggled][toggled] = min(INFTY,bestcost+leastdiff);
				caseToggled:;
			}

			dfs.pop();
		}
		else throw exception();
	}

	dbg_for (auto [a,b] : subtree_bests)
	{
		dbg("next:")<< a[0] << " " << a[1] << "|" << b[0] << " " << b[1];
	}
	ll ans = min(subtree_bests[0][0][0],subtree_bests[0][0][1]);
	if (ans==INFTY){
		cout << "impossible";
	}
	else {
		cout << ans;
	}
}

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