Submission #447262

#	Time	Username	Problem	Language	Result	Execution time	Memory
447262		Aryan_Raina	The Xana coup (BOI21_xanadu)	C++17	100 / 100	110 ms	26372 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
#define ld long double
#define ar array
#define all(a) a.begin(), a.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e12;
const int MOD = 1e9+7;

const int MXN = 100005;
vector<int> g[MXN];
bool omk[MXN];
int dp[2][2][MXN];
// [button][camera on/off]

void dfs(int u, int pu) {
    dp[1][0][u] = dp[1][1][u] = 1;

    vector<int> tmp1, tmp2;
    for (int v : g[u]) if (v != pu) {
        dfs(v, u);
        dp[1][!omk[u]][u] += dp[0][1][v];
        dp[1][omk[u]][u] += dp[0][1][v];
        tmp1.push_back(dp[1][1][v] - dp[0][1][v]);
        dp[0][!omk[u]][u] += dp[0][0][v];
        dp[0][omk[u]][u] += dp[0][0][v];
        tmp2.push_back(dp[1][0][v] - dp[0][0][v]);
    }

    sort(tmp1.begin(), tmp1.end());
    for (int i = 1; i < tmp1.size() && tmp1[i-1] + tmp1[i] < 0; i += 2)
        dp[1][!omk[u]][u] += tmp1[i-1] + tmp1[i];

    if (tmp1.size() > 0) dp[1][omk[u]][u] += tmp1[0];
    else dp[1][omk[u]][u] = INF;
    for (int i = 2; i < tmp1.size() && tmp1[i-1] + tmp1[i] < 0; i += 2)
        dp[1][omk[u]][u] += tmp1[i-1] + tmp1[i]; 

    sort(tmp2.begin(), tmp2.end());
    for (int i = 1; i < tmp2.size() && tmp2[i-1] + tmp2[i] < 0; i += 2)
        dp[0][omk[u]][u] += tmp2[i-1] + tmp2[i];

    if (tmp2.size() > 0) dp[0][!omk[u]][u] += tmp2[0];
    else dp[0][!omk[u]][u] = INF;
    for (int i = 2; i < tmp2.size() && tmp2[i-1] + tmp2[i] < 0; i += 2)
        dp[0][!omk[u]][u] += tmp2[i-1] + tmp2[i];   
}

void solve() {
    int N; cin >> N;
    for (int i = 0; i < N-1; i++) {
        int a, b; cin >> a >> b;
        g[--a].push_back(--b);
        g[b].push_back(a);
    }

    for (int i = 0; i < N; i++) cin >> omk[i];

    dfs(0,0);

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

    if (ans >= INF/2) cout << "impossible\n";
    else cout << ans << '\n';
} 
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 

    int t = 1; //cin >> t;
    while (t--) solve();   
}  

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(int64_t, int64_t)':
xanadu.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 1; i < tmp1.size() && tmp1[i-1] + tmp1[i] < 0; i += 2)
      |                     ~~^~~~~~~~~~~~~
xanadu.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 2; i < tmp1.size() && tmp1[i-1] + tmp1[i] < 0; i += 2)
      |                     ~~^~~~~~~~~~~~~
xanadu.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 1; i < tmp2.size() && tmp2[i-1] + tmp2[i] < 0; i += 2)
      |                     ~~^~~~~~~~~~~~~
xanadu.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 2; i < tmp2.size() && tmp2[i-1] + tmp2[i] < 0; i += 2)
      |                     ~~^~~~~~~~~~~~~

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