Submission #972604

#	Time	Username	Problem	Language	Result	Execution time	Memory
972604		kl0989e	The Xana coup (BOI21_xanadu)	C++17	100 / 100	60 ms	22540 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define all(x) (x).begin(),(x).end()

const int maxn=1e5+10;
vector<vi> graph(maxn);
vector<vi> dp(maxn,vi(4,1e9));// (on,on), (off,off), (off,on), (on,off)
vi onoff(maxn,0);

void dfs(int cur, int prev=-1) {
    if (graph[cur].size()==1 && cur!=0) {
        if (onoff[cur]) {
            dp[cur][0]=0;
            dp[cur][2]=0;
        }
        else {
            dp[cur][1]=0;
            dp[cur][3]=0;
        }
        return;
    }
    int sum1=0,sum2=0;
    int sig1=1,sig2=1;//1=on & 0=off
    int minc1=1e9,minc2=1e9;
    if (!onoff[cur]) {
        sig1=0;
        sig2=0;
    }
    for (auto to:graph[cur]) {
        if (to==prev) {
            continue;
        }
        dfs(to,cur);
        if (dp[to][0]+1<dp[to][1]) {
            sig1=1-sig1;
            sum1+=dp[to][0]+1;
            minc1=min(minc1,dp[to][1]-dp[to][0]-1);
        }
        else {
            sum1+=dp[to][1];
            minc1=min(minc1,dp[to][0]+1-dp[to][1]);
        }
        if (dp[to][3]+1<dp[to][2]) {
            sig2=1-sig2;
            sum2+=dp[to][3]+1;
            minc2=min(minc2,dp[to][2]-dp[to][3]-1);
        }
        else {
            sum2+=dp[to][2];
            minc2=min(minc2,dp[to][3]+1-dp[to][2]);
        }
        sum1=min(int(1e9),sum1);
        sum2=min(int(1e9),sum2);
    }
    //cout << "cur: " << cur << '\n' << sig1 << ' ' << sum1 << ' ' << minc1 << '\n' << sig2 << ' ' << sum2 << ' ' << minc2 << '\n';
    if (sig1) {
        dp[cur][2]=min(sum1,dp[cur][2]);
        dp[cur][1]=min(sum1+minc1,dp[cur][1]);
    }
    else {
        dp[cur][1]=min(sum1,dp[cur][1]);
        dp[cur][2]=min(sum1+minc1,dp[cur][2]);
    }
    if (sig2) {
        dp[cur][0]=min(sum2,dp[cur][0]);
        dp[cur][3]=min(sum2+minc2,dp[cur][3]);
    }
    else {
        dp[cur][3]=min(sum2,dp[cur][3]);
        dp[cur][0]=min(sum2+minc2,dp[cur][0]);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int a,b;
    for (int i=0; i<n-1; i++) {
        cin >> a >> b;
        graph[--a].pb(--b);
        graph[b].pb(a);
    }
    for (int i=0; i<n; i++) {
        cin >> onoff[i];
    }
    dfs(0);
    int ans=min(dp[0][0]+1,dp[0][1]);
    if (ans>=1e9) {
        cout << "impossible\n";
    }
    else {
        cout << ans << '\n';
    }
    /*for (int i=0; i<n; i++) {
        cout << "i: " << i+1 << " - ";
        for (int j=0; j<4; j++) {
            cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }*/
    return 0;
}

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