Submission #605200

#	Time	Username	Problem	Language	Result	Execution time	Memory
605200		M_W	The Xana coup (BOI21_xanadu)	C++17	100 / 100	83 ms	17064 KiB

xanadu

#include <bits/stdc++.h>
#define ii pair<int, int>
using namespace std;
int N;
const int inf = 1000000;
vector<int> adj[100001];
int dp[100001][2][2]; // node, black-white, press-no
int st[100001];

void dfs(int a, int p){
    if(adj[a].size() == 1 && a != 1){
        dp[a][st[a]][0] = 0; dp[a][1 - st[a]][1] = 1;
        // printf(">> %d : %d %d, %d %d\n", a, dp[a][0][0], dp[a][0][1], dp[a][1][0], dp[a][1][1]);
        return;
    }

    int tmp[2][2] = {{inf, inf}, {inf, inf}};
    bool black = true, white = true;
    // shift-no, black-white
    for(auto x : adj[a]){
        if(x == p) continue;
        dfs(x, a);

        int b_p = dp[x][0][1];
        int b_n = dp[x][0][0];

        if(min(b_p, b_n) >= inf) black = false;

        int w_p = dp[x][1][1];
        int w_n = dp[x][1][0];

        if(min(w_p, w_n) >= inf) white = false;

        // printf("%d %d %d %d\n",b_p,b_n,w_p,w_n);

        int bnsh = tmp[0][0] >= inf && tmp[0][1] >= inf ? b_n : min(tmp[0][0] + b_n, tmp[0][1] + b_p);
        int bsh = tmp[0][1] >= inf && tmp[0][0] >= inf ? b_p : min(tmp[0][0] + b_p, tmp[0][1] + b_n);

        int wnsh = tmp[1][0] >= inf && tmp[1][1] >= inf ? w_n : min(tmp[1][0] + w_n, tmp[1][1] + w_p);
        int wsh = tmp[1][1] >= inf && tmp[1][0] >= inf ? w_p : min(tmp[1][0] + w_p, tmp[1][1] + w_n);

        tmp[0][0] = bnsh; tmp[0][1] = bsh; tmp[1][0] = wnsh; tmp[1][1] = wsh; 
    }
    // printf("tmp >> %d : %d %d, %d %d\n", a, tmp[0][0], tmp[0][1], tmp[1][0], tmp[1][1]);
    // no press
    if(black){
        dp[a][st[a]][0] = tmp[0][0];
        dp[a][1 - st[a]][0] = tmp[0][1];
    }
    
    // dp[a][st[a]][0] = tmp[0][0];
    // dp[a][1 - st[a]][0] = tmp[1][0];

    // press
    if(white){
        dp[a][1 - st[a]][1] = tmp[1][0] + 1;
        dp[a][st[a]][1] = tmp[1][1] + 1;
    }
    
    // dp[a][1 - st[a]][1] = tmp[0][1] + 1;
    // dp[a][st[a]][1] = tmp[1][1] + 1;

    // printf(">> %d : %d %d, %d %d\n", a, dp[a][0][0], dp[a][0][1], dp[a][1][0], dp[a][1][1]);
}

int main(){
    scanf("%d", &N);
    for(int i = 1, u, v; i < N; i++){
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= N; i++) scanf("%d", &st[i]);
    for(int i = 1; i <= N; i++){
        dp[i][0][0] = dp[i][0][1] = inf;
        dp[i][1][0] = dp[i][1][1] = inf;
    }
    
    dfs(1, 1);

    if(min(dp[1][0][0], dp[1][0][1]) >= inf) printf("impossible");
    else printf("%d", min(dp[1][0][0], dp[1][0][1]));
}

Compilation message (stderr)

xanadu.cpp: In function 'int main()':
xanadu.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
xanadu.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
xanadu.cpp:73:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     for(int i = 1; i <= N; i++) scanf("%d", &st[i]);
      |                                 ~~~~~^~~~~~~~~~~~~~

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