Submission #553888

#	Time	Username	Problem	Language	Result	Execution time	Memory
553888		new_acc	The Xana coup (BOI21_xanadu)	C++14	100 / 100	67 ms	29116 KiB

xanadu

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const int SS=1<<19;
const int INFi=1e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
ll dp[N][2][2];
vi graf[N];
bool t[N];
void dfs(int v,int o){
	vl curr1,curr2;
	ll sum1=0,sum2=0;
	for(auto u:graf[v]){
		if(u==o) continue;
		dfs(u,v);
		sum1+=dp[u][t[u]][0],sum2+=dp[u][t[u]^1][0];
		curr1.push_back(dp[u][t[u]][1]-dp[u][t[u]][0]),curr2.push_back(dp[u][t[u]^1][1]-dp[u][t[u]^1][0]);
	}
	sort(curr1.begin(),curr1.end()),sort(curr2.begin(),curr2.end());
	dp[v][0][0]=min((ll)INFi,sum1),dp[v][1][1]=min((ll)INFi,sum2);
	dp[v][0][1]=INFi,dp[v][1][0]=INFi;
	ll cnt=0;
	for(int i=0;i<curr1.size();i++){
		cnt+=curr1[i];
		if(!(i&1)) dp[v][1][0]=min(dp[v][1][0],cnt+sum1);
		else dp[v][0][0]=min(dp[v][0][0],cnt+sum1);
	}
	cnt=0;	
	for(int i=0;i<curr2.size();i++){
		cnt+=curr2[i];
		if(!(i&1)) dp[v][0][1]=min(dp[v][0][1],cnt+sum2);
		else dp[v][1][1]=min(dp[v][1][1],cnt+sum2);
	}
	dp[v][1][1]++,dp[v][0][1]++;
	dp[v][1][1]=min(dp[v][1][1],(ll)INFi),dp[v][0][1]=min(dp[v][0][1],(ll)INFi);
}
void solve(){
	int n;
	cin>>n;
	for(int a,b,i=1;i<n;i++){
		cin>>a>>b;
		graf[a].push_back(b),graf[b].push_back(a);
	}
	for(int i=1;i<=n;i++) cin>>t[i];
	dfs(1,1);
	int res=min(dp[1][t[1]][0],dp[1][t[1]][1]);
	if(res==INFi) cout<<"impossible\n";
	else cout<<res<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<curr1.size();i++){
      |              ~^~~~~~~~~~~~~
xanadu.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i=0;i<curr2.size();i++){
      |              ~^~~~~~~~~~~~~

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