제출 #487843

#제출 시각아이디문제언어결과실행 시간메모리
487843cfalasThe Xana coup (BOI21_xanadu)C++14
0 / 100
83 ms8056 KiB
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define INF 10000000 #define MOD 1000000007 #define MID ((l+r)/2) #define HASHMOD 2305843009213693951 #define ll long long #define ull unsigned long long #define F first #define S second typedef pair<ll, ll> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef map<int, int> mii; #define EPS 1e-6 #define FOR(i,n) for(int i=0;i<((int)(n));i++) #define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++) #define FOA(v, a) for(auto v : a) int t, n; vi a, b; vector<vi> adj; int dp[500000][2][2]; int dfs(int s, int x, int xp, int p=0){ if(dp[s][x][xp]!=0) return dp[s][x][xp]; int ans=0; int c = a[s]; if(xp) c = 1-c; if(x) c = 1-c, ans++; if(adj[s].size()==2){ FOA(v, adj[s]){ if(v!=p) ans+= dfs(v, a[v]!=c, x, s); } } else if(adj[s].size()==3){ int a1=0, a2=0; if(c==0){ FOA(v, adj[s]){ if(v!=p) a1+= dfs(v, (x^a[v])==1, x, s); if(v!=p) a2+= dfs(v, (x^a[v])==0, x, s); } } else{ int cnt=0; FOA(v, adj[s]){ if(v!=p) a1+= dfs(v, (x^a[v])==cnt, x, s); if(v!=p) a2+= dfs(v, (x^a[v])!=cnt, x, s); cnt = 1-cnt; } } ans += min(a1, a2); } if(adj[s].size()==1 && c!=0) ans = MOD; dp[s][x][xp] = ans; //cout<<s<<" "<<x<<" "<<xp<<": "<<ans<<endl; return ans; } int main(){ cin>>n; adj.assign(n+1, vi()); FOR(i,n+2) dp[i][0][0] = dp[i][0][1] = dp[i][1][0] = dp[i][1][1] = 1; FOR(i,n-1){ int a, b; cin>>a>>b; adj[a].push_back(b); adj[b].push_back(a); } a.resize(n+1); b.resize(n+1); FOR(i,n){ cin>>a[i+1]; } int ans1 = dfs(1, a[1], 0); int ans2 = dfs(1, 1-a[1], 0); if(ans1 >= MOD && ans2 >= MOD) cout<<"impossible\n"; else cout<<min(ans1, ans2); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...