Submission #1095397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095397		Neco_arc	The Xana coup (BOI21_xanadu)	C++17	100 / 100	41 ms	22108 KiB

xanadu

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "xanadu"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 1e5 + 7
#define int long long

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n;
int a[maxn], dp[maxn][2][2];
vector<int> edges[maxn];

void Minimize(int &x, int y) {
    x = min(x, y);
}

void dfs(int u, int par) {

    int S[] = {0, 0}, cnt[] = {0, 0}, Min[] = {(int) 1e9, (int) 1e9};
    memset(dp[u], 60, sizeof dp[u]);

    for(int v : edges[u]) if(v != par) {
        dfs(v, u);
        fi(i, 0, 1) {
            int t = dp[v][i^1][0] < dp[v][i^1][1] ? 0 : 1;
            S[i] += dp[v][i^1][t], cnt[i] ^= t;
            Min[i] = min(Min[i], dp[v][i^1][t^1] - dp[v][i^1][t]);
        }
    }

    /// su dung thao tac o u
    Minimize(dp[u][a[u] ^ cnt[1] ^ 1][1], S[1] + 1);
    Minimize(dp[u][a[u] ^ cnt[1]][1], S[1] + Min[1] + 1);


    /// ko dung thao tac o u
    Minimize(dp[u][a[u] ^ cnt[0]][0], S[0]);
    Minimize(dp[u][a[u] ^ cnt[0] ^ 1][0], S[0] + Min[0]);
}

void solve()
{

    cin >> n;
    fi(i, 2, n) {
        int x, y; cin >> x >> y;
        edges[x].push_back(y), edges[y].push_back(x);
    }
    fi(i, 1, n) cin >> a[i], a[i] ^= 1;

    dfs(1, 0);
    int ans = 1e9;

    fi(i, 0, 1) ans = min(ans, dp[1][1][i]);

    if(ans == 1e9) cout << "impossible";
    else cout << ans;
}

main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }

    int nTest = 1;
//    cin >> nTest;

    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message (stderr)

xanadu.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 | main()
      | ^~~~
xanadu.cpp: In function 'int main()':
xanadu.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
xanadu.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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