Submission #434959

#	Time	Username	Problem	Language	Result	Execution time	Memory
434959		dqhungdl	The Xana coup (BOI21_xanadu)	C++17	100 / 100	198 ms	23520 KiB

xanadu

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

const int MAX=1e5+5,INF=1e9;
int n,c[MAX],f[MAX][2][2];
vector<int> g[MAX];

void dfs(int u,int p) {
	for(int v:g[u]) {
		if(v==p)
			continue;
		dfs(v,u);
	}
	// Not toggle u
	int sum=0,change=0;
	vector<int> V;
	for(int v:g[u]) {
		if(v==p)
			continue;
		sum+=f[v][0][0];
		V.push_back(f[v][1][0]-f[v][0][0]);
	}
	if(V.size()==0) {
		f[u][0][c[u]]=0;
		f[u][1][c[u]^1]=1;
		return;
	}
	sort(V.begin(),V.end());
	for(int i=0;i<=V.size();i++) {
		if((i+c[u])%2==0)
			f[u][0][0]=min(f[u][0][0],sum+change);
		else
			f[u][0][1]=min(f[u][0][1],sum+change);
		if(i<V.size())
			change+=V[i];
	}
	// Toggle u
	sum=change=0;
	V.clear();
	for(int v:g[u]) {
		if(v==p)
			continue;
		sum+=f[v][0][1];
		V.push_back(f[v][1][1]-f[v][0][1]);
	}
	sort(V.begin(),V.end());
	for(int i=0;i<=V.size();i++) {
		if((i+c[u])%2==0)
			f[u][1][1]=min(f[u][1][1],sum+change+1);
		else
			f[u][1][0]=min(f[u][1][0],sum+change+1);
		if(i<V.size())
			change+=V[i];
	}
}

int32_t main() {
#ifdef ACM
	freopen("input","r",stdin);
#endif
	cin>>n;
	int u,v;
	for(int i=1;i<n;i++) {
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
		cin>>c[i];
	for(int i=1;i<=n;i++)
		f[i][0][0]=f[i][0][1]=f[i][1][0]=f[i][1][1]=INF;
	dfs(1,1);
	int rs=min(f[1][0][0],f[1][1][0]);
	if(rs==INF)
		cout<<"impossible";
	else
		cout<<rs;
}

Compilation message (stderr)

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

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