Submission #676379

#	Time	Username	Problem	Language	Result	Execution time	Memory
676379		YENGOYAN	The Xana coup (BOI21_xanadu)	C++17	0 / 100	83 ms	26820 KiB

xanadu

/*
    //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
    \\                                    //
    //  271828___182845__904523__53602__  \\
    \\  87___47____13______52____66__24_  //
    //  97___75____72______47____09___36  \\
    \\  999595_____74______96____69___67  //
    //  62___77____24______07____66__30_  \\
    \\  35___35____47______59____45713__  //
    //                                    \\
    \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
                                              */

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_map>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>

using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7, inf = 1e18;

int n;
vector<vector<int>> tree;
vector<int> vec;
vector<vector<ll>> dp;

void dfs(int u, int p) {
	for (int v : tree[u]) {
		if (v != p) dfs(v, u);
	}
	ll ans = 0, ans1 = 0;
	vector<ll> delta;
	for (int v : tree[u]) {
		if (v != p) 
		{
			ans += min(dp[v][0], dp[v][1]);
			ans1 += dp[v][1];
		}
	}
 
	if (!vec[u]) {
		ll cur = 0;
		for (int v : tree[u]) {
			//if (v == p) continue;
			if (v != p)
			{
				delta.push_back(dp[v][1] - dp[v][0]);
				cur += dp[v][0];
			}
		}
		sort(delta.begin(), delta.end());
		for (int i = 1; i < delta.size(); i += 2) {
			if (delta[i] + delta[i - 1] <= 0) cur += delta[i] + delta[i - 1];
		}
		dp[u][0] = cur;
	}
	else {
		ll cur = 0;
		for (int v : tree[u]) {
			if (v == p) continue;
			delta.push_back(dp[v][1] - dp[v][0]);
			cur += dp[v][0];
		}
		sort(delta.begin(), delta.end());
		if (!delta.size()) {
			dp[u][0] = 2e15;
			//return;
		}
		else {
			cur += delta[0];
			for (int i = 1; i < delta.size() - 1; i += 2) {
				if (0 >= delta[i] + delta[i + 1]) {
					cur += delta[i] + delta[i + 1];
				}
			}
			dp[u][0] = cur;
		}
	}
	cout << u + 1 << " : " << dp[u][0] << " " << dp[u][1] << "\n";
	// dp[u][0]
}

void solve() {
	cin >> n;
	vec = vector<int>(n);
	tree = vector<vector<int>>(n);
	dp = vector<vector<ll>>(n, vector<ll>(2));
	//sub = vector<int>(n);
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		tree[--u].push_back(--v);
		tree[v].push_back(u);
	}
	for (int i = 0; i < n; ++i) cin >> vec[i];
	//return;
	//fnd_sub(0, -1);
	dfs(0, -1);
	cout << dp[0][0] << " " << dp[0][1] << "\n";
	cout << min(dp[0][0], dp[0][1]) << "\n";	
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	//int ; cin >> _; while (--)
	solve();
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:71:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for (int i = 1; i < delta.size(); i += 2) {
      |                   ~~^~~~~~~~~~~~~~
xanadu.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    for (int i = 1; i < delta.size() - 1; i += 2) {
      |                    ~~^~~~~~~~~~~~~~~~~~

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