oj.uz

답안 #444025

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444025 2021-07-13T02:52:20 Z yungyao The Xana coup (BOI21_xanadu) C++17
55 / 100
 292 ms 19908 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 <assert.h>

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

    queue <int> bfs; bfs.push(g); vis[g] = true;
    while (bfs.size()){
        int x = bfs.front(); bfs.pop();
        invtrs[c] = x; trs[x] = c++;
        for (auto i:adj[x]){
            if (vis[i]){
                hadj[trs[x]].push_back(trs[i]);
                hadj[trs[i]].push_back(trs[x]);
            }
            else if (i != op){
                bfs.push(i);
                vis[i] = true;
            }
        }
    }
    assert (c <= 20);
    for (int mask=0;mask<(1 << c);++mask){
        bool stat_copy[22];
        for (int i=0;i<c;++i) stat_copy[i] = status[invtrs[i]];

        for (int i=0;i<c;++i) if (mask & (1 << i)){
            stat_copy[i] ^= 1;
            for (auto cn:hadj[i]) stat_copy[cn] ^= 1;
        }
        bool ok = true;
        for (int i=1;i<c;++i) if (stat_copy[i]){ok = false; break;}

        if (ok){
            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:145:40: warning: 'g[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
  145 |     vector <int> v1 = findans(g[0],g[1]), v2 = findans(g[1],g[0]);
      |                                        ^
xanadu.cpp:145:40: warning: 'g[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 70 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 71 ms 2644 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 70 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 71 ms 2644 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 70 ms 2636 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 69 ms 2636 KB Output is correct
11 Correct 142 ms 2636 KB Output is correct
12 Correct 215 ms 2636 KB Output is correct
13 Correct 292 ms 2648 KB Output is correct
14 Runtime error 5 ms 5120 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 19852 KB Output is correct
2 Correct 140 ms 19620 KB Output is correct
3 Correct 116 ms 19908 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 19844 KB Output is correct
2 Correct 117 ms 19596 KB Output is correct
3 Correct 132 ms 19908 KB Output is correct
4 Correct 106 ms 6808 KB Output is correct
5 Correct 117 ms 7304 KB Output is correct
6 Correct 129 ms 7320 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 35 ms 4292 KB Output is correct
9 Correct 117 ms 7464 KB Output is correct
10 Correct 120 ms 7480 KB Output is correct
11 Correct 118 ms 8364 KB Output is correct
12 Correct 141 ms 8580 KB Output is correct
13 Correct 121 ms 7084 KB Output is correct
14 Correct 119 ms 7492 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 70 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 71 ms 2644 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 70 ms 2636 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 69 ms 2636 KB Output is correct
11 Correct 142 ms 2636 KB Output is correct
12 Correct 215 ms 2636 KB Output is correct
13 Correct 292 ms 2648 KB Output is correct
14 Runtime error 5 ms 5120 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -