제출 #568118

#제출 시각아이디문제언어결과실행 시간메모리
568118inluminasThe Xana coup (BOI21_xanadu)C++17
0 / 100
81 ms14996 KiB
#include"bits/stdc++.h" using namespace std; #define ll long long #define endl "\n" #define fastio ios_base::sync_with_stdio(false) #define inf LLONG_MAX #define l first #define r second const int lmt=1e5+10; vector<int>adj[lmt]; bool on[lmt]; int dp[lmt][2][2]; void check(int u,int p,int ver){ bool tata=0; int val=0,one=0; vector<int>a; for(int v:adj[u]){ if(v==p) continue; if(dp[v][ver][1]==1e9 && dp[v][ver][0]==1e9){ tata=1; break; }else if(dp[v][ver][0]==1e9){ val+=dp[v][ver][1],one++; }else if(dp[v][ver][1]==1e9){ val+=dp[v][ver][0]; }else{ val+=dp[v][ver][0]; a.push_back(-dp[v][ver][0]+dp[v][ver][1]); } } if(tata) return; sort(a.begin(),a.end()); dp[u][on[u]^((one+ver)%2)][ver]=min(dp[u][on[u]^((one+ver)%2)][ver],val+ver); for(int x:a){ val+=x,one++; dp[u][on[u]^((one+ver)%2)][ver]=min(dp[u][on[u]^((one+ver)%2)][ver],val+ver); } return; } void dfs(int u,int p){ int deg=0; for(int v:adj[u]){ if(v==p) continue; dfs(v,u); deg++; } if(!deg){ dp[u][on[u]][0]=0,dp[u][on[u]^1][1]=1; //cout<<dp[u][0][0]<<" "<<dp[u][0][1]<<" "<<dp[u][1][0]<<" "<<dp[u][1][1]<<endl; return; }else{ check(u,p,0); check(u,p,1); } } int main(){ fastio; int n; cin>>n; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } for(int i=1;i<=n;i++){ bool x; cin>>x; on[i]=x; } for(int i=0;i<=n;i++){ for(int j=0;j<2;j++){ for(int k=0;k<2;k++){ dp[i][j][k]=1e9; } } } dfs(1,-1); int ans=min(dp[1][0][0],dp[1][0][1]); if(ans==1e9) cout<<"Impossible"<<endl; else cout<<ans<<endl; return 0; }
#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...