Submission #659986

#	Time	Username	Problem	Language	Result	Execution time	Memory
659986		Mahdi	The Xana coup (BOI21_xanadu)	C++17	100 / 100	135 ms	26536 KiB

xanadu

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N=1e5+5;
int n, r[N];
ll a[N], b[N], c[N], d[N];
vector<int>g[N];

void dfs(const int &v, const int &p=-1){
    b[v]=d[v]=1;
    vector<int>x, y;
    for(int u: g[v]){
        if(u!=p){
            dfs(u, v);
            a[v]+=a[u];
            c[v]+=a[u];
            x.push_back(b[u]-a[u]);
            b[v]+=c[u];
            d[v]+=c[u];
            y.push_back(d[u]-c[u]);
        }
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    ll aa=1e18, bb=1e18, cc=1e18, dd=1e18;
    if(r[v]){
        aa=0;
        dd=0;
    }
    else{
        bb=0;
        cc=0;
    }
    ll sm=0;
    bool h=r[v];
    for(int u: x){
        sm+=u;
        if(h)
            cc=min(cc, sm);
        else
            aa=min(aa, sm);
        h=!h;
    }
    h=r[v];
    sm=0;
    for(int u: y){
        sm+=u;
        if(h)
            bb=min(bb, sm);
        else
            dd=min(dd, sm);
        h=!h;
    }
    a[v]+=aa;
    b[v]+=bb;
    c[v]+=cc;
    d[v]+=dd;
    ll zz=1e9;
    a[v]=min(a[v], zz);
    b[v]=min(b[v], zz);
    c[v]=min(c[v], zz);
    d[v]=min(d[v], zz);
}

int main(){
    cin>>n;
    for(int i=1;i<n;++i){
        int u, v;
        cin>>u>>v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    for(int i=0;i<n;++i){
        cin>>r[i];
        r[i]=1-r[i];
    }
    dfs(0);
    int z=min(a[0], b[0]);
    if(z>n)
        cout<<"impossible\n";
    else
        cout<<z<<'\n';
}

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