Submission #1236189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236189		erering	The Xana coup (BOI21_xanadu)	C++20	100 / 100	47 ms	34632 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl '\n'
#define int long long
const int N=1e5+5,inf=2e12,MOD=1e9+7;
int dp[N][2][2]; //start and press?
vector<int> adj[N];
int t[N];
void solve(int node,int type,vector<int> vec,int ans){
    sort(vec.begin(),vec.end(),greater<int>());
    int ans2=ans;
    if(type==1)ans2+=vec.back();
    dp[node][0][type]=ans2;
    for(int i=vec.size()-2-type;i>=0;i-=2){
        ans2+=vec[i]; ans2+=vec[i+1];
        dp[node][0][type]=min(dp[node][0][type],ans2);
    }
    ans2=ans;
    if(type==0)ans2+=vec.back();
    dp[node][1][type]=ans2;
    for(int i=vec.size()-3+type;i>=0;i-=2){
        ans2+=vec[i]; ans2+=vec[i+1];
        dp[node][1][type]=min(dp[node][1][type],ans2);
    }
    if(type==1){
        dp[node][0][type]++;
        dp[node][1][type]++;
    }
}
void dfs(int node,int par){
    int ans=0,ans2=0;
    vector<int> vec,vec2;
    for(auto i:adj[node]){
        if(i==par)continue;
        dfs(i,node);
        ans+=dp[i][t[i]][0];
        ans2+=dp[i][t[i]^1][0];
        vec.pb(dp[i][t[i]][1]-dp[i][t[i]][0]);
        vec2.pb(dp[i][t[i]^1][1]-dp[i][t[i]^1][0]);
      //  if(node==1)cout<<dp
    }
    if(vec.empty()){
        dp[node][0][0]=0;
        dp[node][1][1]=1;
       // cout<<node<<' '<<dp[node][t[node]][0]<<' '<<dp[node][t[node]][1]<<endl;
        return;
    }
    solve(node,0,vec,ans);
    solve(node,1,vec2,ans2);
   // cout<<node<<' '<<dp[node][t[node]][0]<<' '<<dp[node][t[node]][1]<<' '<<ans<<endl;
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin>>n;
    for(int i=0;i<n-1;i++){
        int x,y; cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for(int i=1;i<=n;i++){
        cin>>t[i];
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++)dp[i][j][k]=inf;
        }
    }
    dfs(1,0);
    int sol=min(dp[1][t[1]][0],dp[1][t[1]][1]);
   // cout<<dp[2][0][0]<<' '<<dp[3][1][1]<<endl;
    if(sol>n)cout<<"impossible";
    else cout<<sol;
}

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