Submission #444030

#	Time	Username	Problem	Language	Result	Execution time	Memory
444030		yungyao	The Xana coup (BOI21_xanadu)	C++17	55 / 100	1033 ms	19880 KiB

xanadu

using namespace std;
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <vector>
#include <memory.h>

typedef long long LL;
typedef pair<int,int> pii;
#define F first
#define S second
#define mkp make_pair
#define iter(x) x.begin(),x.end()
#define MEM(s,e) memset(s,e,sizeof(s))

const int maxn = 1e5+100,inf = 1e9;


int dp[maxn][2][2]; //index, t/f, on/off
bool status[maxn];

vector <int> adj[maxn];

void dfs(int x,int fr){
    int ldp[2][2][2],c=0;
    for (auto s:adj[x]) if (s != fr){
        dfs(s,x);
        for (int i=0;i<2;++i) for (int j=0;j<2;++j){
            ldp[c][i][j] = dp[s][i][j];
        }
        ++c;
    }
    if (!c){
        if (status[x]){
            dp[x][1][0] = 0;
            dp[x][0][1] = 1;
            dp[x][0][0] = inf;
            dp[x][1][1] = inf;
        }
        else{
            dp[x][0][0] = 0;
            dp[x][1][1] = 1;
            dp[x][1][0] = inf;
            dp[x][0][1] = inf;
        }
    }
    else if (c == 1){
        if (status[x]){
            dp[x][0][0] = ldp[0][0][1];
            dp[x][0][1] = ldp[0][1][0] + 1;
            dp[x][1][0] = ldp[0][0][0];
            dp[x][1][1] = ldp[0][1][1] + 1;
        }
        else{
            dp[x][0][0] = ldp[0][0][0];
            dp[x][0][1] = ldp[0][1][1] + 1;
            dp[x][1][0] = ldp[0][0][1];
            dp[x][1][1] = ldp[0][1][0] + 1;
        }
    }
    else{
        if (status[x]){
            dp[x][0][0] = min(inf,min(ldp[0][0][1] + ldp[1][0][0],ldp[0][0][0] + ldp[1][0][1]));
            dp[x][0][1] = min(inf,min(ldp[0][1][0] + ldp[1][1][0],ldp[0][1][1] + ldp[1][1][1]) + 1);
            dp[x][1][0] = min(inf,min(ldp[0][0][0] + ldp[1][0][0],ldp[0][0][1] + ldp[1][0][1]));
            dp[x][1][1] = min(inf,min(ldp[0][1][1] + ldp[1][1][0],ldp[0][1][0] + ldp[1][1][1]) + 1);
        }
        else{
            dp[x][0][0] = min(inf,min(ldp[0][0][0] + ldp[1][0][0],ldp[0][0][1] + ldp[1][0][1]));
            dp[x][0][1] = min(inf,min(ldp[0][1][1] + ldp[1][1][0],ldp[0][1][0] + ldp[1][1][1]) + 1);
            dp[x][1][0] = min(inf,min(ldp[0][0][1] + ldp[1][0][0],ldp[0][0][0] + ldp[1][0][1]));
            dp[x][1][1] = min(inf,min(ldp[0][1][0] + ldp[1][1][0],ldp[0][1][1] + ldp[1][1][1]) + 1);
        }
    }
}

int n,mxsub[maxn];
int findg(int x,int fr){
    int cnt = 1;
    for (auto i:adj[x]) if (i != fr){
        int r = findg(i,x);
        cnt += r;
        mxsub[x] = max(mxsub[x],r);
    }
    mxsub[x] = max(mxsub[x],n - cnt);
    return cnt;
}

#include <bitset>

vector <int> findans(int g,int op){
    bitset <100> tf[100];
    vector <int> ret(4,inf); //00 for f/off, 01 for f/on, 10 for t/off, 11 for t/on
    bool vis[100]{};
    int trs[100]{},invtrs[100]{},c = 0;

    queue <int> bfs; bfs.push(g); vis[g] = true;
    while (bfs.size()){
        int x = bfs.front(); bfs.pop();
        invtrs[c] = x; trs[x] = c++;
        tf[trs[x]][trs[x]] = true;
        for (auto i:adj[x]){
            if (vis[i]){
                tf[trs[x]][trs[i]] = true;
                tf[trs[i]][trs[x]] = true;
            }
            else if (i != op){
                bfs.push(i);
                vis[i] = true;
            }
        }
    }
    bitset <100> sta;
    for (int i=0;i<c;++i) sta[i] = status[invtrs[i]];

    for (int mask=0;mask<(1 << c);++mask){
        bitset <100> stat_copy = sta;
        for (int i=0;i<c;++i) if (mask & (1 << i)){
            stat_copy ^= tf[i];
        }
        if (stat_copy.count() - int(stat_copy[0]) > 0) continue;

        if (stat_copy[0] and (mask & 1)) ret[3] = min(ret[3],__builtin_popcount(mask));
        else if (stat_copy[0] and !(mask & 1)) ret[2] = min(ret[2],__builtin_popcount(mask));
        else if (!stat_copy[0] and (mask & 1)) ret[1] = min(ret[1],__builtin_popcount(mask));
        else if (!stat_copy[0] and !(mask & 1)) ret[0] = min(ret[0],__builtin_popcount(mask));
    }

    return ret;
}

void brutesolve(){
    findg(1,0);
    int g[2],c = 0;
    for (int i=1;i<=n;++i) if (mxsub[i] <= n/2) g[c++] = i;
    if (c == 1) g[1] = adj[g[0]][0];

    vector <int> v1 = findans(g[0],g[1]), v2 = findans(g[1],g[0]);
    int ans = min(min(v1[0]+v2[0],v1[3]+v2[3]),min(v1[1]+v2[2],v1[2]+v2[1]));
    
    if (ans >= inf) cout << "impossible\n";
    else cout << ans << '\n';
}

int main(){
    cin >> n;
    for (int _=n-1;_--;){
        int u,v;

        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i=1;i<=n;++i) cin >> status[i];
    if (n <= 40) {brutesolve(); return 0;}

    for (int i=1;i<=n;++i) if (adj[i].size() == 1){
        dfs(i,0);
        int ans = min(dp[i][0][0],dp[i][0][1]);
        if (ans >= inf) cout << "impossible\n";
        else cout << ans << '\n';
        break;
    }
    return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'void brutesolve()':
xanadu.cpp:142:40: warning: 'g[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
  142 |     vector <int> v1 = findans(g[0],g[1]), v2 = findans(g[1],g[0]);
      |                                        ^
xanadu.cpp:142:40: warning: 'g[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]

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