제출 #1206225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206225		dosts	The Xana coup (BOI21_xanadu)	C++17	100 / 100	43 ms	23880 KiB

xanadu

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e17;

const int N = 1e5+1;

int dp[N][2][2];
vi edges[N],c(N);
int dfs(int node,int p,int press,int color) {
    if (~dp[node][press][color]) return dp[node][press][color];
    dp[node][press][color] = inf;
    int f[2];
    f[c[node]^press] = press,f[c[node]^press^1] = inf;
    for (auto it : edges[node]) {
        if (it == p) continue;
        int a = dfs(it,node,0,press);
        int b = dfs(it,node,1,press);
        int f0 = f[0],f1 = f[1];
        f[0] = min({inf,f1+b,f0+a}),f[1] = min({inf,f0+b,f1+a});
    }
    for (int i = 0;i<2;i++) dp[node][press][i] = f[i];
    return dp[node][press][color];
}

void solve() {  
    int n;
    cin >> n;
    memset(dp,-1,sizeof dp);
    for (int i=1;i<n;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    for (int i=1;i<=n;i++) cin >> c[i];
    dfs(1,1,0,0),dfs(1,1,1,0);
    int ans = min(dp[1][0][0],dp[1][1][0]);
    if (ans >= inf) cout << "impossible\n";
    else cout << ans << '\n';
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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