oj.uz

Submission #444030

# Submission time Handle Problem Language Result Execution time Memory
444030 2021-07-13T03:09:15 Z yungyao The Xana coup (BOI21_xanadu) C++17
55 / 100
 1000 ms 19880 KB 
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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 37 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 42 ms 2636 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 37 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 42 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 37 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 37 ms 2636 KB Output is correct
11 Correct 76 ms 2636 KB Output is correct
12 Correct 108 ms 2636 KB Output is correct
13 Correct 151 ms 2636 KB Output is correct
14 Execution timed out 1033 ms 2636 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 19776 KB Output is correct
2 Correct 114 ms 19656 KB Output is correct
3 Correct 115 ms 19880 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 19856 KB Output is correct
2 Correct 118 ms 19584 KB Output is correct
3 Correct 135 ms 19832 KB Output is correct
4 Correct 102 ms 6852 KB Output is correct
5 Correct 112 ms 7280 KB Output is correct
6 Correct 112 ms 7320 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 39 ms 4288 KB Output is correct
9 Correct 116 ms 7468 KB Output is correct
10 Correct 111 ms 7428 KB Output is correct
11 Correct 114 ms 8272 KB Output is correct
12 Correct 118 ms 8556 KB Output is correct
13 Correct 106 ms 7076 KB Output is correct
14 Correct 121 ms 7400 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 37 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 42 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 37 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 37 ms 2636 KB Output is correct
11 Correct 76 ms 2636 KB Output is correct
12 Correct 108 ms 2636 KB Output is correct
13 Correct 151 ms 2636 KB Output is correct
14 Execution timed out 1033 ms 2636 KB Time limit exceeded
15 Halted 0 ms 0 KB -