제출 #1287074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287074		user736482	The Xana coup (BOI21_xanadu)	C++17	100 / 100	63 ms	29452 KiB

xanadu

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353LL
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 2000000000000000099LL
#define pii pair<ll,ll>
#define pip pair<ll,pii>
#define ppi pair<pii,ll>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define X 18
#define all(x) x.begin(),x.end()
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
ll fct[1000007];
ll fp(ll a,ll b){
    if(b<0)b+=MOD-1;
    ll c=1;while(b){if(b&1)c=(c*a)%MOD;a=(a*a)%MOD;b/=2;}
    return c;
}
ll n,a,b;
bool cz[100007];
vi g[100007];
ppp pol(ll v,ll pop){// czy potrzeba, czydajemy
    ppp ns;
    ll bf=0,bn=0,mnf=INF,mnn=INF;
    bool wf=cz[v]^1,wn=cz[v];
    for(auto i : g[v]){
        if(i!=pop){
            ppp ak=pol(i,v);
            if(ak.ff.ff<ak.ff.ss){
                bn+=ak.ff.ff;
                mnn=min(mnn,ak.ff.ss-ak.ff.ff);
            }
            else{
                wn^=1;
                bn+=ak.ff.ss;
                mnn=min(mnn,ak.ff.ff-ak.ff.ss);
            }
            if(ak.ss.ff<ak.ss.ss){
                bf+=ak.ss.ff;
                mnf=min(mnf,ak.ss.ss-ak.ss.ff);
            }
            else{
                wf^=1;
                bf+=ak.ss.ss;
                mnf=min(mnf,ak.ss.ff-ak.ss.ss);
            }
        }
    }
    if(wn){
        ns.ss.ff=bn;
        ns.ff.ff=bn+mnn;
    }
    else{
        ns.ss.ff=bn+mnn;
        ns.ff.ff=bn;
    }
    if(wf){
        ns.ss.ss=bf+1;
        ns.ff.ss=bf+mnf+1;
    }
    else{
        ns.ss.ss=bf+mnf+1;
        ns.ff.ss=bf+1;
    }
    //cout<<v<<" "<<ns<<"\n";
    return ns;
}
void solve(){
    cin>>n;
    for(ll i=1;i<n;i++){
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }
    for(ll i=1;i<=n;i++){
        cin>>cz[i];
    }
    ppp pm=pol(1,1);
    ll ns=min(pm.ff.ff,pm.ff.ss);
    if(ns>n)cout<<"impossible";
    else cout<<ns;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    fct[0]=1;
    for(ll i=1;i<1000007;i++)fct[i]=(fct[i-1]*i)%MOD;
    ll t=1;
    //cin>>t;
    while(t--)solve();
}

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