제출 #652657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
652657		1zaid1	The Xana coup (BOI21_xanadu)	C++17	0 / 100	1086 ms	7380 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n';
 
const int M = 1e5+5, MOD = 1e9+7;
vector<int> node[M];
int c[M];

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n;
    cin >> n;

    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;

        node[a].push_back(b);
        node[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) cin >> c[i];

    map<int, int> fr, cum;
    int ans = n+1, pp = 0;
    for (int i = 1; i <= n; i++) pp += c[i]*(1<<i)/2;
    for (int m = 1; m < (1<<(n/2)); m++) {
        int x = 0;
        for (int i = 1; i <= n/2; i++) {
            if (m&(1<<(i-1))) {
                for (int k:node[i]) x += (1<<(k-1));
                x += (1<<(i-1));
            }
        }

        if (x == pp) ans = min(ans, (int)__builtin_popcount(m));
        if (!fr[x]) fr[x] = __builtin_popcount(m), cum[x] = m;
        else fr[x] = min(fr[x], (int)__builtin_popcount(m));
    }

    for (int m = 1; m < (1<<(n-n/2)); m++) {
        int x = 0;
        for (int i = 0; i < n; i++) x += c[i+1]*(1<<i);
        for (int i = n/2+1; i <= n; i++) {
            if (m&(1<<(i-n/2-1))) {
                for (int j:node[i]) x ^= (1<<(j-1));
                x ^= (1<<(i-1));
            }
        }

        if (fr[x]) ans = min(ans, fr[x]+__builtin_popcount(m));
        if (!x) ans = min(ans, (int)__builtin_popcount(m));
    }

    cout << (ans>n?"impossible":to_string(ans)) << endl;

    return 0;
}
 
/*
5
1 2
1 3
2 4
2 5
0 1 0 1 1

5
1 2
2 3
3 4
4 5
0 1 1 1 1
*/

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