oj.uz

Submission #444014

# Submission time Handle Problem Language Result Execution time Memory
444014 2021-07-13T01:25:40 Z yungyao The Xana coup (BOI21_xanadu) C++17
10 / 100
 128 ms 21268 KB 
using namespace std;
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <vector>
#include <memory.h>

typedef long long LL;
typedef pair<int,int> pii;
#define F first
#define S second
#define mkp make_pair
#define iter(x) x.begin(),x.end()
#define MEM(s,e) memset(s,e,sizeof(s))

const int maxn = 1e5+100,inf = 1e9;
#include <climits>


int dp[maxn][2][2]; //index, t/f, on/off
bool status[maxn];

vector <int> adj[maxn];

void dfs(int x,int fr){
    int ldp[2][2][2],c=0;
    for (auto s:adj[x]) if (s != fr){
        dfs(s,x);
        for (int i=0;i<2;++i) for (int j=0;j<2;++j){
            ldp[c][i][j] = dp[s][i][j];
        }
        ++c;
    }
    if (!c){
        if (status[x]){
            dp[x][1][0] = 0;
            dp[x][0][1] = 1;
            dp[x][0][0] = inf;
            dp[x][1][1] = inf;
        }
        else{
            dp[x][0][0] = 0;
            dp[x][1][1] = 1;
            dp[x][1][0] = inf;
            dp[x][0][1] = inf;
        }
    }
    else if (c == 1){
        if (status[x]){
            dp[x][0][0] = ldp[0][0][1];
            dp[x][0][1] = ldp[0][1][0] + 1;
            dp[x][1][0] = ldp[0][0][0];
            dp[x][1][1] = ldp[0][1][1] + 1;
        }
        else{
            dp[x][0][0] = ldp[0][0][0];
            dp[x][0][1] = ldp[0][1][1] + 1;
            dp[x][1][0] = ldp[0][0][1];
            dp[x][1][1] = ldp[0][1][0] + 1;
        }
    }
    else{
        if (status[x]){
            dp[x][0][0] = min(ldp[0][0][1] + ldp[1][0][0],ldp[0][0][0] + ldp[1][0][1]);
            dp[x][0][1] = min(ldp[0][1][0] + ldp[1][1][0],ldp[0][1][1] + ldp[1][1][1]) + 1;
            dp[x][1][0] = min(ldp[0][0][0] + ldp[1][0][0],ldp[0][0][1] + ldp[1][0][1]);
            dp[x][1][1] = min(ldp[0][1][1] + ldp[1][1][0],ldp[0][1][0] + ldp[1][1][1]) + 1;
        }
        else{
            dp[x][0][0] = min(ldp[0][0][0] + ldp[1][0][0],ldp[0][0][1] + ldp[1][0][1]);
            dp[x][0][1] = min(ldp[0][1][1] + ldp[1][1][0],ldp[0][1][0] + ldp[1][1][1]) + 1;
            dp[x][1][0] = min(ldp[0][0][1] + ldp[1][0][0],ldp[0][0][0] + ldp[1][0][1]);
            dp[x][1][1] = min(ldp[0][1][0] + ldp[1][1][0],ldp[0][1][1] + ldp[1][1][1]) + 1;
        }
    }
}

int main(){
    int n;

    cin >> n;
    for (int _=n-1;_--;){
        int u,v;

        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i=1;i<=n;++i) cin >> status[i];
    for (int i=1;i<=n;++i) if (adj[i].size() == 1){
        dfs(i,0);
        int ans = min(dp[i][0][0],dp[i][0][1]);
        if (ans >= inf) cout << "impossible\n";
        else cout << ans << '\n';
        break;
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5196 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5196 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 21192 KB Output is correct
2 Correct 118 ms 20932 KB Output is correct
3 Correct 118 ms 21188 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 21148 KB Output is correct
2 Correct 117 ms 20932 KB Output is correct
3 Correct 128 ms 21268 KB Output is correct
4 Incorrect 105 ms 8024 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5196 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -