Submission #418083

#	Time	Username	Problem	Language	Result	Execution time	Memory
418083		balbit	The Xana coup (BOI21_xanadu)	C++14	100 / 100	93 ms	24364 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define int ll

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT



const int maxn = 1e5+6;

int dp[maxn][2][2]; // v, me, par
vector<int >g[maxn];
bool lit[maxn];
int  n;
void dfs(int v, int p) {

    for (int u : g[v]) {
        if (u != p) {
            dfs(u,v);
        }
    }

    REP(tk, 2) {
        int me = lit[v] ^ tk;
        int sig0 = 0;
        vector<int> go;
        for (int u : g[v]) {
            if (u != p) {
                sig0 += dp[u][tk][0];
                go.pb(dp[u][tk][1] - dp[u][tk][0]);
            }
        }
        sort(ALL(go));
        int sm = 0;
        REP(t, SZ(go)+1) {
            MN(dp[v][me^(t%2)][tk], sig0 + sm + tk);
            if (t == SZ(go) || go[t] > n) break;
            sm += go[t];
        }
        bug(v, tk, dp[v][0][tk], dp[v][1][tk]);
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin>>n;
    REP1(i,n) REP(b,2) REP(c,2) {
        dp[i][b][c] = n+1;
    }
    REP(i,n-1) {
        int a,b; cin>>a>>b; g[a].pb(b); g[b].pb(a);
    }
    REP1(i,n) {
        cin>>lit[i];
    }
    dfs(1, -1);
    int re = min(dp[1][0][1], dp[1][0][0]);
    if (re > n) cout<<"impossible"<<endl;
    else cout<<re<<endl;

}

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