Submission #448517

#	Time	Username	Problem	Language	Result	Execution time	Memory
448517		mariowong	The Xana coup (BOI21_xanadu)	C++14	100 / 100	121 ms	32988 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

long long n,u,v,dfsorder[100005],dp[100005][5][5],ans1,ans2,a[100005];
//first 0 1 closed?
//second 0 1 pressed?
vector <long long> edge[100005],v1,v2;
bool vis[100005];
queue <long long> q;
void dfs(int x){
	vis[x]=true;
	for (int i=0;i<edge[x].size();i++){
		if (!vis[edge[x][i]]){
			dfsorder[x]++;
			dfs(edge[x][i]);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i=1;i<n;i++){
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	for (int i=1;i<=n;i++){
		cin >> a[i];
	}
	dfs(1);
	for (int i=1;i<=n;i++){
		if (dfsorder[i] == 0)
		q.push(i);
		vis[i]=false;
		dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=n+1;
	}
	while (!q.empty()){
		u=q.front(); q.pop(); vis[u]=true;
		ans1=ans2=0; v1.clear(); v2.clear();
		for (int i=0;i<edge[u].size();i++){
			if (vis[edge[u][i]]){
				ans1+=dp[edge[u][i]][0][0]; // off 
				v1.push_back(dp[edge[u][i]][0][1]-dp[edge[u][i]][0][0]);
				ans2+=dp[edge[u][i]][1][0]; // on 
				v2.push_back(dp[edge[u][i]][1][1]-dp[edge[u][i]][1][0]);
			}
			else
			{
				dfsorder[edge[u][i]]--;
				if (dfsorder[edge[u][i]] == 0)
				q.push(edge[u][i]);
			}
		}
		dp[u][a[u]][0]=min(ans1,dp[u][a[u]][0]); dp[u][1-a[u]][1]=min(ans2+1,dp[u][1-a[u]][1]);
		sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end());
		for (int i=0;i<v1.size();i++){
			ans1+=v1[i]; ans2+=v2[i];
			if (i%2 == 0){
				dp[u][1-a[u]][0]=min(dp[u][1-a[u]][0],ans1);
				dp[u][a[u]][1]=min(dp[u][a[u]][1],ans2+1);
			}
			else
			{
				dp[u][a[u]][0]=min(dp[u][a[u]][0],ans1);
				dp[u][1-a[u]][1]=min(dp[u][1-a[u]][1],ans2+1);
			}
		}
	}
/*	for (int i=1;i<=n;i++){
		cout << dp[i][0][0] << " " << dp[i][0][1] << " " << dp[i][1][0] << " " << dp[i][1][1] << "\n";
	}*/
	if (min(dp[1][0][0],dp[1][0][1]) == n+1)
	cout << "impossible\n";
	else
	cout << min(dp[1][0][0],dp[1][0][1]) << "\n";
	return 0;
}
//1 3 6 10
//2 7 9
//4 5 11
//8

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(int)':
xanadu.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i=0;i<edge[x].size();i++){
      |               ~^~~~~~~~~~~~~~~
xanadu.cpp: In function 'int main()':
xanadu.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (int i=0;i<edge[u].size();i++){
      |                ~^~~~~~~~~~~~~~~
xanadu.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (int i=0;i<v1.size();i++){
      |                ~^~~~~~~~~~

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