oj.uz

Submission #398572

# Submission time Handle Problem Language Result Execution time Memory
398572 2021-05-04T14:49:51 Z Jarif_Rahman The Xana coup (BOI21_xanadu) C++17
50 / 100
 120 ms 28804 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e9;

int n;

vector<vector<int>> v;
vector<vector<vector<ll>>> dp;
vector<int> state;

void dfs(int nd, int ss){
    if(v[nd].size() == 1 && ss != -1){
        dp[nd][0][0] = (state[nd]?inf:0);
        dp[nd][0][1] = (state[nd]?1:inf);
        dp[nd][1][0] = (state[nd]?0:inf);
        dp[nd][1][1] = (state[nd]?inf:1);
        return;
    }
    for(int x: v[nd]) if(x != ss) dfs(x, nd);

    dp[nd][0][1] = 1;
    dp[nd][1][1] = 1;

    int cnt = 0;
    ll mn = inf;
    for(int x: v[nd]) if(x != ss){
        dp[nd][0][0] += min(dp[x][0][0], dp[x][0][1]);
        dp[nd][1][0] += min(dp[x][0][0], dp[x][0][1]);
        if(dp[x][0][0] > dp[x][0][1]) cnt++;
        mn = abs(dp[x][0][0]-dp[x][0][1]);
    }
    if(state[nd]){
        if(cnt%2 == 0) dp[nd][0][0]+=mn;
        else dp[nd][1][0]+=mn;
    }
    else{
        if(cnt%2 == 0) dp[nd][1][0]+=mn;
        else dp[nd][0][0]+=mn;
    }

    cnt = 0;
    mn = inf;
    for(int x: v[nd]) if(x != ss){
        dp[nd][0][1] += min(dp[x][1][0], dp[x][1][1]);
        dp[nd][1][1] += min(dp[x][1][0], dp[x][1][1]);
        if(dp[x][1][0] > dp[x][1][1]) cnt++;
        mn = abs(dp[x][1][0]-dp[x][1][1]);
    }
    if(!state[nd]){
        if(cnt%2 == 0) dp[nd][0][1]+=mn;
        else dp[nd][1][1]+=mn;
    }
    else{
        if(cnt%2 == 0) dp[nd][1][1]+=mn;
        else dp[nd][0][1]+=mn;
    }
    dp[nd][0][0] = min(dp[nd][0][0], inf);
    dp[nd][1][0] = min(dp[nd][1][0], inf);
    dp[nd][0][1] = min(dp[nd][0][1], inf);
    dp[nd][1][1] = min(dp[nd][1][1], inf);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    v.resize(n);
    state.resize(n);
    dp.assign(n, vector<vector<ll>>(2, vector<ll>(2, 0)));
    for(int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b; a--, b--;
        v[a].pb(b);
        v[b].pb(a);
    }
    for(int &x: state) cin >> x;
    dfs(0, -1);
    ll ans = min(dp[0][0][0], dp[0][0][1]);
    if(ans >= inf) cout << "impossible\n";
    else cout << ans << "\n";
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 28456 KB Output is correct
2 Correct 89 ms 28116 KB Output is correct
3 Correct 94 ms 28804 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 28484 KB Output is correct
2 Correct 83 ms 28136 KB Output is correct
3 Correct 82 ms 28612 KB Output is correct
4 Correct 89 ms 20044 KB Output is correct
5 Correct 108 ms 21900 KB Output is correct
6 Correct 105 ms 22288 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 27 ms 7620 KB Output is correct
9 Correct 110 ms 22112 KB Output is correct
10 Correct 105 ms 22476 KB Output is correct
11 Correct 114 ms 22312 KB Output is correct
12 Correct 120 ms 22972 KB Output is correct
13 Correct 94 ms 21024 KB Output is correct
14 Correct 100 ms 22296 KB Output is correct

Subtask #5
0 / 30.0

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