Submission #416980

#	Time	Username	Problem	Language	Result	Execution time	Memory
416980		aryan12	The Xana coup (BOI21_xanadu)	C++17	100 / 100	102 ms	28208 KiB

xanadu

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

const int N = 1e5 + 5;
vector<int> g[N];
int val[N];
int dp[N][2][2];

/*
dp[i][j][k] => currently in the ith node, the ith subtree is safe (except the last layer, maybe) 
j => current condition of the node (0 = off, 1 = on)
k => whether the parents value has been altered or not (0 = no, 1 = yes)
*/

void dfs(int node, int par) {
	if(g[node].size() == 1) {
		dp[node][val[node]][0] = 0;
		dp[node][1LL - val[node]][1] = 1;
		return;
	}
	vector<int> children[2];
	int sum0 = 0, sum1 = 0;
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i] != par) {
			dfs(g[node][i], node);
			sum0 += dp[g[node][i]][0][0];
			sum1 += dp[g[node][i]][1][0];
			if(dp[g[node][i]][0][1] != INT_MAX) {
				children[0].push_back(dp[g[node][i]][0][1] - dp[g[node][i]][0][0]);
			}
			if(dp[g[node][i]][1][1] != INT_MAX) {
				children[1].push_back(dp[g[node][i]][1][1] - dp[g[node][i]][1][0]);
			}
		}
	}
	for(int i = 0; i < 2; i++) {
		sort(children[i].begin(), children[i].end());
	}
	/*cout << "node = " << node << "\n";
	cout << "sum0 = " << sum0 << ", sum1 = " << sum1 << "\n";
	for(int i = 0; i < 2; i++) {
		cout << "iteration = " << i << "\n";
		for(int j = 0; j < children[i].size(); j++) {
			cout << children[i][j] << " ";
		}
		cout << "\n";
	}*/
	int prev0 = sum0, prev1 = sum1;


/* if all the children have their cameras off */

	//Subpart 1: not to change the value of node
	dp[node][val[node]][0] = min(dp[node][val[node]][0], sum0);
	for(int i = 0; i < children[0].size(); i += 2) {
		if(i + 1 == children[0].size())
			break;
		sum0 += (children[0][i] + children[0][i + 1]);
		dp[node][val[node]][0] = min(dp[node][val[node]][0], sum0);
	}

	//Subpart 2: change the value of the node
	if(children[0].size() != 0) {
		sum0 = prev0 + children[0][0];
		dp[node][1LL - val[node]][0] = min(dp[node][1LL - val[node]][0], sum0);
	}
	for(int i = 1; i < children[0].size(); i += 2) {
		if(i + 1 == children[0].size())
			break;
		sum0 += (children[0][i] + children[0][i + 1]);
		dp[node][1LL - val[node]][0] = min(dp[node][1LL - val[node]][0], sum0);
	}


/* if all the children have their cameras on 
   Note: parent and node have to be tempered, so its reverse */

	
	//Subpart 1: not to change the value of node 
	if(children[1].size() != 0) {
		sum1 = prev1 + children[1][0] + 1;
		dp[node][val[node]][1] = min(dp[node][val[node]][1], sum1);
	}
	for(int i = 1; i < children[1].size(); i += 2) {
		if(i + 1 == children[1].size())
			break;
		sum1 += children[1][i] + children[1][i + 1];
		dp[node][val[node]][1] = min(dp[node][val[node]][1], sum1);
	}

	//Subpart 2: change the value of node
	sum1 = prev1 + 1;
	dp[node][1LL - val[node]][1] = sum1;
	for(int i = 0; i < children[1].size(); i += 2) {
		if(i + 1 == children[1].size())
			break;
		sum1 += children[1][i] + children[1][i + 1];
		dp[node][1LL - val[node]][1] = min(dp[node][1LL - val[node]][1], sum1);
	}
}

void Solve() {
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < 2; j++) {
			for(int k = 0; k < 2; k++) {
				dp[i][j][k] = INT_MAX;
			}
		}
	}
	int n;
	cin >> n;
	for(int i = 1; i < n; i++) {
		int v, u;
		cin >> v >> u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	g[1].push_back(-1);
	for(int i = 1; i <= n; i++) {
		cin >> val[i];
	}
	dfs(1, -1);
	int ans = min(dp[1][0][0], dp[1][0][1]);
	if(ans == INT_MAX) {
		cout << "impossible\n";
	}
	else {
		cout << ans << "\n";
	}
	//cout << min(dp[1][0][0], dp[1][0][1]) << "\n";
	/*for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 2; j++) {
			for(int k = 0; k < 2; k++) {
				cout << "dp[" << i << "][" << j << "][" << k << "] = " << dp[i][j][k] << "\n";
			}
			cout << "\n\n";
		}
		cout << "\n\n\n\n";
	}*/
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:24:19: 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]
   24 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
xanadu.cpp:56:19: 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]
   56 |  for(int i = 0; i < children[0].size(); i += 2) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~
xanadu.cpp:57:12: 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]
   57 |   if(i + 1 == children[0].size())
      |      ~~~~~~^~~~~~~~~~~~~~~~~~~~~
xanadu.cpp:68:19: 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]
   68 |  for(int i = 1; i < children[0].size(); i += 2) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~
xanadu.cpp:69:12: 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]
   69 |   if(i + 1 == children[0].size())
      |      ~~~~~~^~~~~~~~~~~~~~~~~~~~~
xanadu.cpp:85:19: 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]
   85 |  for(int i = 1; i < children[1].size(); i += 2) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~
xanadu.cpp:86:12: 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]
   86 |   if(i + 1 == children[1].size())
      |      ~~~~~~^~~~~~~~~~~~~~~~~~~~~
xanadu.cpp:95:19: 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]
   95 |  for(int i = 0; i < children[1].size(); i += 2) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~
xanadu.cpp:96:12: 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]
   96 |   if(i + 1 == children[1].size())
      |      ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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