Submission #540527

#	Time	Username	Problem	Language	Result	Execution time	Memory
540527		Stickfish	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	545 ms	308320 KiB

prison

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 2e6 + 123;
vector<int> edg[MAXN];
int rt[MAXN];

int init(int n) {
    int t;
    cin >> t;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    vector<pair<int, int>> stck;
    vector<int> vl(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        stck.push_back({a[i], i});
        while (stck.size() && t - stck.back().first < i - stck.back().second)
            stck.pop_back();
        if (stck.size()) {
            vl[i] = stck.back().second;
        } else {
            ++ans;
            vl[i] = n + 1;
        }
    }
    //for (int i = 0; i < n; ++i)
        //cout << vl[i] << ' ';
    //cout << endl;
    vector<int> way;
    for (int i = n - 1; i >= 0; --i) {
        while (way.size() && vl[way.back()] > i) {
            way.pop_back();
        }
        if (vl[i] >= i) {
            rt[i] = -1;
            continue;
        }
        if (vl[i] < i && way.size()) {
            rt[i] = way.back();
            edg[way.back()].push_back(i);
        } else {
            rt[i] = 0;
            edg[0].push_back(i);
        }
        way.push_back(i);
    }
    //for (int i = 0; i < n; ++i) {
        //cout << rt[i] << ' ';
    //}
    //cout << endl;
    return ans;
}

bool cmpsize(vector<int>* v0, vector<int>* v1) {
    return v0->size() < v1->size();
}

vector<int>* dfs(int v) {
    if (edg[v].empty()) {
        vector<int>* ans = new vector<int>(1);
        (*ans)[0] = 1;
        return ans;
    }
    vector<vector<int>*> vs;
    for (auto u : edg[v]) {
        vs.push_back(dfs(u));
    }
    int mxi = max_element(vs.begin(), vs.end(), cmpsize) - vs.begin();
    vector<int>* ans = vs[mxi];
    for (int i = 0; i < vs.size(); ++i) {
        if (i == mxi)
            continue;
        vector<int>* t = vs[i];
        if ((*t)[0] > (*ans)[0])
            swap((*t)[0], (*ans)[0]);
        for (auto x : *t)
            ans->push_back(x);
        delete t;
    }
    ++(*ans)[0];
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, d;
    cin >> n >> d;
    int neut = init(n);
    vector<int> vvv = *dfs(0);
    sort(vvv.rbegin(), vvv.rend());
    int ans = 0;
    for (int i = 0; i < vvv.size() && i < d; ++i)
        ans += vvv[i];
    cout << n - ans - neut + 1 << endl;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<int>* dfs(int)':
prison.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int>*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < vs.size(); ++i) {
      |                     ~~^~~~~~~~~~~
prison.cpp: In function 'int main()':
prison.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i = 0; i < vvv.size() && i < d; ++i)
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 25 / 25
• Subtask 6: 20 / 20