제출 #401013

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

xanadu

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

const int INF=1e9;

int n;
int arr[100005];
vector<int> al[100005];

int memo[100005][2][2];
int dfs(int i,int p,int on,int toggle){
	if (memo[i][on][toggle]!=-1) return memo[i][on][toggle];
	
	//if toggle=false, then our children must be on=false
	//else children must be on=true
	
	int val[2]={INF,INF};
	val[arr[i]]=0;
	
	for (auto &it:al[i]){
		if (it==p) continue;
		
		int tf=dfs(it,i,toggle,false);
		int tt=dfs(it,i,toggle,true);
		
		int temp[2]={min({val[0]+tf,val[1]+tt,INF}),
					 min({val[0]+tt,val[1]+tf,INF})};
		swap(val,temp);
	}
	
	//cout<<i<<" "<<on<<" "<<toggle<<" "<<val[on]+toggle<<endl;
	return memo[i][on][toggle]=val[on^toggle]+toggle;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n;
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	
	rep(x,1,n+1) cin>>arr[x];
	
	memset(memo,-1,sizeof(memo));
	
	int ans=min(dfs(1,-1,0,0),dfs(1,-1,0,1));
	
	//cout<<dfs(1,-1,0,0)<<endl;
	//cout<<dfs(1,-1,0,1)<<endl;
	
	if (ans<1e9) cout<<ans<<endl;
	else cout<<"impossible"<<endl;
}

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