제출 #487870

#제출 시각아이디문제언어결과실행 시간메모리
487870cfalasThe Xana coup (BOI21_xanadu)C++14
10 / 100
116 ms23388 KiB
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define INF 10000000 #define MOD ((ll)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; ll dp[200000][2][2]; ll dfs(int s, int x, int xp, int p=0){ if(dp[s][x][xp]!=-1) return dp[s][x][xp]; ll ans=0; int c = a[s]; if(xp) c = 1-c; if(x) c = 1-c, ans++; int ccnt=0; FOA(v, adj[s]) if(v!=p) ccnt++; if(ccnt==1){ //cout<<s<<" "<<x<<" "<<xp<<" C 1\n"; FOA(v, adj[s]){ if(v!=p) ans+= dfs(v, c, x, s); } } else if(ccnt==2){ ll a1=0, a2=0; int cnt=0; FOA(v, adj[s]){ if(v==p) continue; a1+= dfs(v, cnt, x, s); a2+= dfs(v, 1-cnt, x, s); if(c) cnt = 1-cnt; } ans += min(a1, a2); } else if(ccnt==0 && c!=0) ans = MOD; else if(ccnt>2) return 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); a[0] = 0; FOR(i,n){ cin>>a[i+1]; } ll ans1 = dfs(1, 0, 0); ll ans2 = dfs(1, 1, 0); if(ans1 >= MOD && ans2 >= MOD) cout<<"impossible\n"; else cout<<min(ans1, ans2)<<endl; }
#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...