Submission #1216562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216562		kokoxuya	The Xana coup (BOI21_xanadu)	C++20	100 / 100	108 ms	42488 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x  << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x  << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x  << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define debu4(x,y,z,a) (cerr << #x  << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< " "<<a<<"\n")
#define bitout(x,y) {\
	cerr << #x << " : ";\
	for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
	cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
	cerr << "outputting" << #j<< ":\n";\
	for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
	cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
#define defN 100001
vector<vector<int>>adjlist(defN);
vector<vector<int>>childlist(defN);
vector<vector<int>>depths;
vector<bool>visited(defN,false);

void dfs(int cn,int cd)
{
	visited[cn]=true;
	if(depths.size()==cd){depths.pb(vector<int>());}
	depths[cd].pb(cn);
	
	for(int to:adjlist[cn])
	{
		if(visited[to])continue;
		childlist[cn].pb(to);
		dfs(to,cd+1);
	} 
}

signed main()
{
    int t1,t2,t3,t4;
    mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	int n;cin>>n;
	vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(2,vector<int>(2,INT_MAX)));
	//are you black or white
	//did you turn or not
	
	for(int a=1;a<n;a++)
	{
		cin>>t1>>t2;
		adjlist[t1].pb(t2);
		adjlist[t2].pb(t1);
	}
	dfs(1,0);
	
	int maxdepth=depths.size()-1;
	vector<bool>onn(n+1);
	for(int i=1;i<=n;i++)
	{
		cin>>t1;
		onn[i]=t1;
	}
	
	
	for(int i=maxdepth;i>=0;i--)
	{
		for(int node:depths[i])
		{
			if(childlist[node].size()==0)
			{
				//debu2(childlist[node].size(),node);
				dp[node][onn[node]][0]=0;
				dp[node][!onn[node]][1]=1;
			}
			else
			{
				//do for all whites +flip and no flip
				//do for all blacks +flip and no flip
				//you do a thereafter flip if its the second run
				bool firsttype=0;
				for(int ii=0;ii<2;ii++)
				{
					int currans=0;
					priority_queue<int,vector<int>,greater<int>>pq;
					for(int x:childlist[node])
					{
						currans+=dp[x][firsttype][0];
						pq.push(dp[x][firsttype][1]-dp[x][firsttype][0]);
					}
					
					bool now=firsttype?1-onn[node]:onn[node];
					dp[node][now][firsttype]=currans+firsttype;
					//debu4(node,now,firsttype,currans+firsttype);
					
					while(!pq.empty())
					{
						now^=1;
						currans+=(pq.top());
						pq.pop();
						//debu4(node,now,firsttype,currans+firsttype);
						dp[node][now][firsttype]=min(dp[node][now][firsttype],currans+firsttype);
					}
					
					firsttype^=1;
				}
			}
		}
	}
	
	int ans=min(dp[1][0][1],dp[1][0][0]);
	if(ans>=INT_MAX)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