Submission #933893

#	Time	Username	Problem	Language	Result	Execution time	Memory
933893		codefox	The Xana coup (BOI21_xanadu)	C++14	100 / 100	61 ms	28496 KiB

xanadu

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define arr array<int, 2>
#define int long long

int inf = 1e9;

vector<vector<int>> graph;
vector<int> state;
vector<array<arr, 2>> opt;

void dfs(int i, int p)
{
    opt[i][0][0] = inf;
    opt[i][0][1] = inf;
    opt[i][1][0] = inf;
    opt[i][1][1] = inf;

    if (graph[i].size() == 1 && i != 0)
    {
        int s = state[i];
        opt[i][s][0] = 0;
        opt[i][s][1] = inf;
        if (s == 1) s = 0;
        else s = 1;
        opt[i][s][0] = inf;
        opt[i][s][1] = 1;
        return;
    }
    vector<int> on;
    vector<int> off; 
    int sumon = 0;
    int sumoff = 0;
    for (int ele:graph[i])
    {
        if (ele == p) continue;
        dfs(ele, i);

        sumon += opt[ele][1][0];
        on.push_back(opt[ele][1][1]-opt[ele][1][0]);

        sumoff += opt[ele][0][0];
        off.push_back(opt[ele][0][1]-opt[ele][0][0]);
    }
    sort(on.begin(), on.end(), less<int>());
    sort(off.begin(), off.end(), less<int>());

    int s = state[i];
    int ns;
    if (s == 0) ns = 1;
    else ns = 0;


    for (int j = 0; j <= on.size(); j++)
    {
        if (j%2) opt[i][s][1] = min(opt[i][s][1], sumon+1); 
        else opt[i][ns][1] = min(opt[i][ns][1], sumon+1);
        if (j < on.size()) sumon+=on[j];
    }

    for (int j = 0; j <= off.size(); j++)
    {
        if (j%2) opt[i][ns][0] = min(opt[i][ns][0], sumoff); 
        else opt[i][s][0] = min(opt[i][s][0], sumoff);
        if (j < off.size()) sumoff+=off[j];
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n;
    cin >> n;
    graph.assign(n, vector<int>());
    state.assign(n, 0);
    opt.assign(n, array<arr, 2>());
    
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for (int i = 0; i < n; i++) cin >> state[i];

    dfs(0, -1);

    /*
    for (int i = 0; i < n; i++)
    {
        cout << opt[i][0][0] << " " << opt[i][0][1] << endl;
        cout << opt[i][1][0] << " " << opt[i][1][1] << endl;
    }
    */

    int mn = min(opt[0][0][0], opt[0][0][1]);
    if (mn > n) cout << "impossible\n";
    else cout << mn << "\n";

    return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:57:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int j = 0; j <= on.size(); j++)
      |                     ~~^~~~~~~~~~~~
xanadu.cpp:61:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if (j < on.size()) sumon+=on[j];
      |             ~~^~~~~~~~~~~
xanadu.cpp:64:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int j = 0; j <= off.size(); j++)
      |                     ~~^~~~~~~~~~~~~
xanadu.cpp:68:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if (j < off.size()) sumoff+=off[j];
      |             ~~^~~~~~~~~~~~

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