Submission #442459

#	Time	Username	Problem	Language	Result	Execution time	Memory
442459		Ozy	The Xana coup (BOI21_xanadu)	C++17	0 / 100	69 ms	25032 KiB

xanadu

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000

struct x{
    lli sum;
    lli usa;
    lli dif;
};

lli n,a,b;
lli dp[4][MAX+2], inicial[MAX+2];
vector<lli> hijos[MAX+2];

void DFS(lli pos, lli padre) {

    x on,off;
    on.dif = off.dif = -1;
    on.usa = off.usa = 0;
    on.sum = off.sum = 0;

    for (auto h : hijos[pos]) {
        if (h == padre) continue;

        DFS(h,pos);

        // on - 0,1
        a = min(dp[0][h],dp[1][h]);
        if (a == -1) {
            a = max(dp[0][h],dp[1][h]);
            if (a == -1) {
                dp[0][pos] = -1;
                dp[2][pos] = -1;
            }
            else {
                on.sum += a;
                if (dp[0][h] == a) on.usa++;
            }
        }
        else {
            on.sum += a;
            if (dp[0][h] == a) on.sum++;

            a = abs(dp[0][h] - dp[1][h]);
            if (on.dif == -1) on.dif = a;
            else on.dif = min(on.dif,a);
        }

        //off - 2,3
        a = min(dp[2][h],dp[3][h]);
        if (a == -1) {
            a = max(dp[2][h],dp[3][h]);
            if (a == -1) {
                dp[1][pos] = -1;
                dp[3][pos] = -1;
            }
            else {
                off.sum += a;
                if (dp[2][h] == a) off.usa++;
            }
        }
        else {
            off.sum += a;
            if (dp[2][h] == a) off.sum++;

            a = abs(dp[2][h] - dp[3][h]);
            if (off.dif == -1) off.dif = a;
            else off.dif = min(off.dif,a);
        }
    }

    //0
    if (dp[0][pos] != -1) {
        a = on.usa + inicial[pos];
        b = on.sum+1;
        if (a%2 == 1) {
            if (on.dif == -1) b = -1;
            else b += on.dif;
        }

        dp[0][pos] = b;
    }

    //1
    if (dp[1][pos] != -1) {
        a = off.usa + inicial[pos];
        b = off.sum;
        if (a%2 == 0) {
            if (off.dif == -1) b = -1;
            else b += off.dif;
        }

        dp[1][pos] = b;
    }

    //2
    if (dp[2][pos] != -1) {
        a = on.usa + inicial[pos];
        b = on.sum+1;
        if (a%2 == 0) {
            if (on.dif == -1) b = -1;
            else b += on.dif;
        }

        dp[2][pos] = b;
    }

    //3
    if (dp[3][pos] != -1) {
        a = off.usa + inicial[pos];
        b = off.sum;
        if (a%2 == 1) {
            if (off.dif == -1) b = -1;
            else b += off.dif;
        }

        dp[3][pos] = b;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    rep(i,1,n-1) {
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
    }
    rep(i,1,n) cin >> inicial[i];

    DFS(1,0);
    a = min(dp[2][1],dp[3][1]);
    if (a == -1) a = max(dp[2][1],dp[3][1]);

    if (a < 0) cout << "impossible";
    else cout << a;

    //rep(i,1,n) {rep(j,0,3) debug(dp[j][i]); cout << endl;}
}

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