oj.uz

답안 #444028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444028 2021-07-13T03:00:43 Z yungyao The Xana coup (BOI21_xanadu) C++17
55 / 100
 1000 ms 20072 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[100]; 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[100]{};
    int trs[100]{},invtrs[100]{};

    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;
            }
        }
    }
    bool stat_copy[100];
    for (int i=0;i<c;++i) stat_copy[i] = status[invtrs[i]];
    for (int mask=0;mask<(1 << c);++mask){
        if (mask) for (int i=0;i<c;++i) if ((mask ^ (mask-1)) & (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:143:40: warning: 'g[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
  143 |     vector <int> v1 = findans(g[0],g[1]), v2 = findans(g[1],g[0]);
      |                                        ^
xanadu.cpp:143:40: warning: 'g[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 33 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 27 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 26 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 22 ms 2652 KB Output is correct
11 Correct 42 ms 2636 KB Output is correct
12 Correct 65 ms 2636 KB Output is correct
13 Correct 86 ms 2636 KB Output is correct
14 Execution timed out 1084 ms 2636 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 19824 KB Output is correct
2 Correct 124 ms 19624 KB Output is correct
3 Correct 117 ms 19836 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 19908 KB Output is correct
2 Correct 122 ms 19596 KB Output is correct
3 Correct 143 ms 20072 KB Output is correct
4 Correct 113 ms 6912 KB Output is correct
5 Correct 124 ms 7244 KB Output is correct
6 Correct 131 ms 7364 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 38 ms 4312 KB Output is correct
9 Correct 118 ms 7464 KB Output is correct
10 Correct 127 ms 7520 KB Output is correct
11 Correct 134 ms 8412 KB Output is correct
12 Correct 118 ms 8524 KB Output is correct
13 Correct 111 ms 7044 KB Output is correct
14 Correct 122 ms 7360 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 33 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 27 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 26 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 22 ms 2652 KB Output is correct
11 Correct 42 ms 2636 KB Output is correct
12 Correct 65 ms 2636 KB Output is correct
13 Correct 86 ms 2636 KB Output is correct
14 Execution timed out 1084 ms 2636 KB Time limit exceeded
15 Halted 0 ms 0 KB -