Submission #1056369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056369		Piokemon	The Xana coup (BOI21_xanadu)	C++17	100 / 100	35 ms	17780 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 100'000;
int a[N+9];
vector<int> graf[N+9];
ll dp[N+9][2][2];
ll dp2[N+9][2][2];

void dfs(int v, int par){
    if (graf[v].size()==1 && v!=1){
        dp[v][a[v]][0]=0;
        dp[v][1-a[v]][1]=1;
        dp[v][a[v]][1]=1e9;
        dp[v][1-a[v]][0]=1e9;
        return;
    }
    int nr=1;
    dp2[0][0][0]=0; dp2[0][0][1]=1e9;
    dp2[0][1][0]=0; dp2[0][1][1]=1e9;
    ll s0=0,s1=0;
    for (int x:graf[v]){
        if (x==par)continue;
        dfs(x,v);
    }
    for (int x:graf[v]){
        if (x==par)continue;
        for (int z=0;z<2;z++){
            dp2[nr][z][0]=min(dp2[nr-1][z][0]+dp[x][z][0],dp2[nr-1][z][1]+dp[x][z][1]);
            dp2[nr][z][1]=min(dp2[nr-1][z][0]+dp[x][z][1],dp2[nr-1][z][1]+dp[x][z][0]);
        }
        nr++;
    }
    dp[v][0][0]=dp2[nr-1][0][a[v]];
    dp[v][0][1]=dp2[nr-1][1][1-a[v]]+1;
    dp[v][1][0]=dp2[nr-1][0][1-a[v]];
    dp[v][1][1]=dp2[nr-1][1][a[v]]+1;

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,u,v;
    cin >> n;
    for (int x=1;x<n;x++){
        cin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
    for (int x=1;x<=n;x++){
        cin >> a[x];
    }
    dfs(1,-1);
    /*for (int x=1;x<=n;x++){
        for (int y=0;y<2;y++){
            for (int z=0;z<2;z++) cout << x << ' ' << y << ' ' << z << ' ' << dp[x][y][z] << '\n';
        }
        cout << '\n';
    }*/
    ll temp = min(dp[1][0][0],dp[1][0][1]);
    if (temp>n) cout << "impossible\n";
    else cout << temp << '\n';
    return 0;
    
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:22:8: warning: unused variable 's0' [-Wunused-variable]
   22 |     ll s0=0,s1=0;
      |        ^~
xanadu.cpp:22:13: warning: unused variable 's1' [-Wunused-variable]
   22 |     ll s0=0,s1=0;
      |             ^~

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