Submission #971512

#	Time	Username	Problem	Language	Result	Execution time	Memory
971512		CyberCow	The Xana coup (BOI21_xanadu)	C++17	100 / 100	58 ms	16988 KiB

xanadu

#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((x).size())
typedef long long ll;
using ull = unsigned long long;
using namespace std;
mt19937 rnd(348502);
ll mod1 = 998244353;
ll mod = 1e9 + 7;
const ll N = 100010;

vector<int> v[N];
ll dp[N][2][2];
int a[N];

void Dfs(int g, int p)
{
    for (auto to : v[g])
    {
        if (to != p)
        {
            Dfs(to, g);
        }
    }
    ll ans = 0, qan = 0, mipox = 1e9;
    for (auto to : v[g])
    {
        if (to != p)
        {
            mipox = min(mipox, abs(dp[to][0][0] - dp[to][0][1]));
            if (dp[to][0][0] < dp[to][0][1])
            {
                ans += dp[to][0][0];
            }
            else
            {
                ans += dp[to][0][1];
                qan++;
            }
        }
    }
    if ((qan + a[g]) % 2 == 0)
    {
        dp[g][0][0] = ans;
        dp[g][1][0] = ans + mipox;
    }
    else
    {
        dp[g][1][0] = ans;
        dp[g][0][0] = ans + mipox;
    }
    ans = 0, qan = 0, mipox = 1e9;
    for (auto to : v[g])
    {
        if (to != p)
        {
            mipox = min(mipox, abs(dp[to][1][0] - dp[to][1][1]));
            if (dp[to][1][0] < dp[to][1][1])
            {
                ans += dp[to][1][0];
            }
            else
            {
                ans += dp[to][1][1];
                qan++;
            }
        }
    }
    if ((qan + a[g] + 1) % 2 == 0)
    {
        dp[g][0][1] = ans + 1;
        dp[g][1][1] = ans + mipox + 1;
    }
    else
    {
        dp[g][1][1] = ans + 1;
        dp[g][0][1] = ans + mipox + 1;
    }
}

void solve()
{
    int n, i, j, x, y;
    cin >> n;
    for ( i = 0; i < n - 1; i++)
    {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for ( i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    Dfs(1, -1);
    if (min(dp[1][0][1], dp[1][0][0]) >= 1e9)
    {
        cout << "impossible";
    }
    else
    {
        cout << min(dp[1][0][1], dp[1][0][0]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'void solve()':
xanadu.cpp:102:15: warning: unused variable 'j' [-Wunused-variable]
  102 |     int n, i, j, x, y;
      |               ^

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