oj.uz

Submission #695396

# Submission time Handle Problem Language Result Execution time Memory
695396 2023-02-05T05:02:24 Z Duy_e Ball Machine (BOI13_ballmachine) C++14
100 / 100
 206 ms 24988 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define nd second
#define st first
#define rep(i, n, m) for (ll i = n; i <= m; i ++)
#define rrep(i, n, m) for (ll i = n; i >= m; i --)
using namespace std;
const long long N = 2e5 + 5;
int n, q, a[N], full[N], mi[N], up[20][N], pos[N];
vector <int> d[N], order;

void dfs(int u) {
    mi[u] = u;
    for (int v: d[u])
        dfs(v), mi[u] = min(mi[u], mi[v]);
}

void dfs2(int u) {
    for (int v: d[u]) dfs2(v);
    order.push_back(u);
}

priority_queue <pii, vector <pii>, greater <pii>> st;
void del(int u) {
    int cnt = 0;
    rrep(i, 19, 0) if (full[up[i][u]])
        u = up[i][u], cnt += 1 << i;
    full[u] = false;
    st.push({pos[u], u});
    cout << cnt << '\n';
}

int cur = 0;
void add(int k) {
    int lst = 0;
    while (st.size() && k) {
        lst = st.top().nd;
        st.pop();
        k --;
        full[lst] = true;
    }

    while (k) k --, lst = order[cur ++], full[lst] = true;
    cout << lst << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("A.ans", "w", stdout);
    cin >> n >> q;
    rep(i, 1, n) {
        int p; cin >> p;
        d[p].push_back(i);
        up[0][i] = p;
    }

    dfs(0);
    rep(i, 1, 19) rep(j, 1, n)
        up[i][j] = up[i - 1][up[i - 1][j]];

    auto cmp = [&] (int u, int v) { return mi[u] < mi[v]; };
    rep(i, 1, n) sort(d[i].begin(), d[i].end(), cmp);

    dfs2(0);
    rep(i, 0, order.size() - 1) pos[order[i]] = i;
    int t, x;

    while (q --) {
        cin >> t >> x;
        if (t == 1) add(x);
        if (t == 2) del(x);
    }

    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:6:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i, n, m) for (ll i = n; i <= m; i ++)
......
   67 |     rep(i, 0, order.size() - 1) pos[order[i]] = i;
      |         ~~~~~~~~~~~~~~~~~~~~~~         
ballmachine.cpp:67:5: note: in expansion of macro 'rep'
   67 |     rep(i, 0, order.size() - 1) pos[order[i]] = i;
      |     ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 106 ms 13160 KB Output is correct
3 Correct 70 ms 12660 KB Output is correct
4 Correct 4 ms 5088 KB Output is correct
5 Correct 5 ms 5188 KB Output is correct
6 Correct 5 ms 5292 KB Output is correct
7 Correct 5 ms 5164 KB Output is correct
8 Correct 6 ms 5204 KB Output is correct
9 Correct 9 ms 5716 KB Output is correct
10 Correct 26 ms 7372 KB Output is correct
11 Correct 108 ms 13608 KB Output is correct
12 Correct 65 ms 12652 KB Output is correct
13 Correct 115 ms 12724 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8704 KB Output is correct
2 Correct 172 ms 20124 KB Output is correct
3 Correct 66 ms 16020 KB Output is correct
4 Correct 55 ms 10260 KB Output is correct
5 Correct 78 ms 10020 KB Output is correct
6 Correct 58 ms 9572 KB Output is correct
7 Correct 52 ms 9424 KB Output is correct
8 Correct 28 ms 8704 KB Output is correct
9 Correct 152 ms 20516 KB Output is correct
10 Correct 145 ms 20120 KB Output is correct
11 Correct 120 ms 19200 KB Output is correct
12 Correct 153 ms 18720 KB Output is correct
13 Correct 112 ms 20540 KB Output is correct
14 Correct 77 ms 16016 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 13500 KB Output is correct
2 Correct 146 ms 20192 KB Output is correct
3 Correct 153 ms 20352 KB Output is correct
4 Correct 101 ms 17848 KB Output is correct
5 Correct 116 ms 17500 KB Output is correct
6 Correct 84 ms 17476 KB Output is correct
7 Correct 95 ms 16484 KB Output is correct
8 Correct 114 ms 20432 KB Output is correct
9 Correct 153 ms 21832 KB Output is correct
10 Correct 124 ms 21428 KB Output is correct
11 Correct 197 ms 21372 KB Output is correct
12 Correct 187 ms 20176 KB Output is correct
13 Correct 173 ms 24988 KB Output is correct
14 Correct 84 ms 18276 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 20788 KB Output is correct
2 Correct 160 ms 20096 KB Output is correct
3 Correct 90 ms 22536 KB Output is correct
4 Correct 204 ms 20748 KB Output is correct
5 Correct 155 ms 20172 KB Output is correct
6 Correct 120 ms 19344 KB Output is correct
7 Correct 149 ms 20180 KB Output is correct
8 Correct 100 ms 22516 KB Output is correct
9 Correct 78 ms 16008 KB Output is correct