oj.uz

Submission #442459

# Submission time Handle Problem Language Result Execution time Memory
442459 2021-07-07T18:24:11 Z Ozy The Xana coup (BOI21_xanadu) C++17
0 / 100
 69 ms 25032 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 25032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 24932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -