Submission #828928

#	Time	Username	Problem	Language	Result	Execution time	Memory
828928		QwertyPi	The Xana coup (BOI21_xanadu)	C++14	100 / 100	96 ms	18860 KiB

xanadu

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

const int N = 1e5 + 11;
const int INF = 1 << 30;
int dp[N][2][2];
vector<int> G[N];
int a[N];

int chmin(int& x, int y){
	x = min(x, y); return x;
}
void dfs(int v, int pa = -1){
	int ch = 0;
	int d[2][2] = {{INF, INF}, {INF, INF}};
	for(auto u : G[v]){
		if(u == pa) continue; ch++; dfs(u, v);
	}

	for(int x = 0; x < 2; x++){
		int b[2][2] = {{0, INF}, {INF, INF}};
		for(auto u : G[v]){
			if(u == pa) continue;
			for(int z = 0; z < 2; z++){
				for(int y = 0; y < 2; y++){
					chmin(b[1][(z + y) % 2], b[0][z] + dp[u][x][y]);
				}
			}
			for(int y = 0; y < 2; y++) swap(b[0][y], b[1][y]), b[1][y] = INF;
		}
		for(int y = 0; y < 2; y++){
			dp[v][a[v] ^ y ^ x][x] = b[0][y] + x;
		}
	}

	if(ch == 0){
		dp[v][a[v]][0] = 0;
		dp[v][!a[v]][1] = 1;
		return;
	}
}

int32_t main(){
	int n; cin >> n;
	for(int i = 0; i < n - 1; i++){
		int u, v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}

	memset(dp, 0x3f, sizeof(dp));
	dfs(1);
	int ans = min(dp[1][0][0], dp[1][0][1]);

	cout << (ans > N ? "impossible" : to_string(ans)) << endl;
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:21:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |   if(u == pa) continue; ch++; dfs(u, v);
      |   ^~
xanadu.cpp:21:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |   if(u == pa) continue; ch++; dfs(u, v);
      |                         ^~
xanadu.cpp:19:6: warning: unused variable 'd' [-Wunused-variable]
   19 |  int d[2][2] = {{INF, INF}, {INF, INF}};
      |      ^

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