Submission #1111326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111326		imarn	The Xana coup (BOI21_xanadu)	C++14	100 / 100	64 ms	21576 KiB

xanadu

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
vector<int>g[mxn];
int col[mxn]{0};
ll dp[mxn][4]{0};
void sol(int u,int p){
    dp[u][0]=dp[u][1]=dp[u][2]=dp[u][3]=1e9;
    int sz1=0,sz2=0;
    ll sm1=0,sm2=0;
    ll mn1=1e9,mn2=1e9;
    for(auto v:g[u]){
        if(v==p)continue;
        sol(v,u);
        if(dp[v][0]>dp[v][2]){
            sm1+=dp[v][2];
            sz1++;
            mn1=min(mn1,dp[v][0]-dp[v][2]);
        }else sm1+=dp[v][0],mn1=min(mn1,dp[v][2]-dp[v][0]);
        if(dp[v][1]>dp[v][3]){
            sm2+=dp[v][3];
            sz2++;
            mn2=min(mn2,dp[v][1]-dp[v][3]);
        }else sm2+=dp[v][1],mn2=min(mn2,dp[v][3]-dp[v][1]);
    }
    if(g[u].size()==1&&u!=1){
        if(!col[u])dp[u][0]=0,dp[u][1]=1e9,dp[u][2]=1e9,dp[u][3]=1;
        else dp[u][0]=inf,dp[u][1]=0,dp[u][2]=1,dp[u][3]=inf;
        return;
    }
    //if(u==3)cout<<sm1<<' '<<sm2<<' '<<sz1<<' '<<sz2<<'\n';
    if(!col[u]){
        if(sz1&1)dp[u][0]=sm1+mn1,dp[u][1]=sm1;
        else dp[u][0]=sm1,dp[u][1]=sm1+mn1;
        if(sz2&1)dp[u][2]=1+sm2,dp[u][3]=1+sm2+mn2;
        else dp[u][2]=1+sm2+mn2,dp[u][3]=1+sm2;
    }
    else {
        if(!(sz1&1))dp[u][0]=sm1+mn1,dp[u][1]=sm1;
        else dp[u][0]=sm1,dp[u][1]=sm1+mn1;
        if(!(sz2&1))dp[u][2]=1+sm2,dp[u][3]=1+sm2+mn2;
        else dp[u][2]=1+sm2+mn2,dp[u][3]=1+sm2;
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n-1;i++){
        int a,b;cin>>a>>b;g[a].pb(b);g[b].pb(a);
    }for(int i=1;i<=n;i++)cin>>col[i];sol(1,1);
    ll rs=min(dp[1][0],dp[1][2]);
    if(rs>=1e9)cout<<"impossible";
    else cout<<rs;
}

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