이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
const int MAX = 100010;
int n;
int val[MAX];
vi edge[MAX];
vi ch[MAX];
int dp[MAX][2][2]; // dp[v][v is 1][parent of v is switched]
void dfs(int v, int pv){
for(int i : edge[v]){
if(i == pv) continue;
ch[v].pb(i);
dfs(i, v);
}
}
void solve(int v){
dp[v][0][0] = dp[v][0][1] = dp[v][1][0] = dp[v][1][1] = INF;
for(int i : ch[v]){
solve(i);
}
int sz = szof(ch[v]);
FOR(mask, 0, (1<<sz) - 1, 1){
vi state;
FOR(i, 0, sz-1, 1){
if(mask & (1<<i)) state.pb(1);
else state.pb(0);
}
// dp[v][?][0] :
// all childs = 0 -> do not flip v
// pick dp[u][0][?] for all childs u
int new_val_v = val[v];
int dp_sum = 0;
FOR(i, 0, sz-1, 1){
int u = ch[v][i];
new_val_v ^= state[i];
dp_sum += dp[u][0][state[i]];
}
dp[v][new_val_v][0] = min(dp[v][new_val_v][0], dp_sum);
// dp[v][?][1] :
// all childs = 1 -> flip v
// pick dp[u][1][?] for all childs u
new_val_v = val[v];
dp_sum = 0;
FOR(i, 0, sz-1, 1){
int u = ch[v][i];
new_val_v ^= state[i];
dp_sum += dp[u][1][state[i]];
}
// flip v : upd. new_val_v, dp_sum
new_val_v ^= 1;
dp_sum += 1;
dp[v][new_val_v][1] = min(dp[v][new_val_v][1], dp_sum);
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
FOR(i, 1, n-1, 1){
int u, v;
cin>>u>>v;
edge[u].pb(v);
edge[v].pb(u);
}
FOR(i, 1, n, 1){
cin>>val[i];
}
dfs(1, -1);
solve(1);
int res = min(dp[1][0][0], dp[1][0][1]);
if(res < INF) cout<<res<<'\n';
else cout<<"impossible"<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |