oj.uz

Submission #518331

# Submission time Handle Problem Language Result Execution time Memory
518331 2022-01-23T12:17:33 Z Ai7081 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 196 ms 21928 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const bool debug = 0;

int n, q, p[N][20], op, x, fen[N], L, pos[N], mi[N];
vector<int> adj[N], ord;
bool mark[N];

void add(int i, int val) {
    for (; i<=n; i+=i&(-i)) fen[i] += val;
    return;
}

int sum(int i) {
    int ret = 0;
    for (; i>0; i-=i&(-i)) ret += fen[i];
    return ret;
}

int find_first(int l, int r) {
    if (l == r) return l;
    int m = (l+r)/2;
    if (sum(m) == 0) return find_first(m+1, r);
    else return find_first(l, m);
}

void find_min(int v) {
    for (int i=1; i<=L; i++) p[v][i] = p[p[v][i-1]][i-1];
    mi[v] = v;
    for (auto to : adj[v]) {
        find_min(to);
        mi[v] = min(mi[v], mi[to]);
    }
    return;
}

void find_ord(int v) {
    for (auto to : adj[v]) {
        find_ord(to);
    }
    ord.push_back(v);
    return;
}

pair<int, int> find_lift(int v) {
    int ti = 0;
    for (int i=L; i>=0; i--) {
        if (!mark[p[v][i]]) v = p[v][i], ti += pow(2, i);
    }
    return make_pair(v, ti);
}

bool cmp(int i, int j) {
    return mi[i] < mi[j];
}

int main() {
    scanf(" %d %d", &n, &q);
    L = ceil(log2(n + 1));
    for (int i=1; i<=n; i++) {
        scanf(" %d", &p[i][0]);
        adj[p[i][0]].push_back(i);
    }

    find_min(adj[0][0]);
    for (int i=1; i<=n; i++) sort(adj[i].begin(), adj[i].end(), cmp);

    ord.push_back(0);
    find_ord(adj[0][0]);
    for (int i=1; i<=n; i++) pos[ord[i]] = i;

    if (debug) {
        printf("ord : ");
        for (auto it : ord) printf("%d ", it);
        printf("\npos : ");
        for (int i=0; i<=n; i++) printf("%d ", pos[i]);
        printf("\n");
        for (int i=1; i<=n; i++) {
            printf("lift %d : ", i);
            for (int j=0; j<=L; j++) printf("%d ", p[i][j]);
            printf("\n");
        }
    }

    mark[0] = true;
    for (int i=1; i<=n; i++) add(i, 1), mark[i] = true;
    while (q--) {
        scanf(" %d %d", &op, &x);
        if (op == 1) {
            int idx;
            for (int i=1; i<=x; i++) {
                idx = find_first(1, n);
                add(idx, -1);
                mark[ord[idx]] = false;
            }
            printf("%d\n", ord[idx]);
        }
        else {
            pair<int, int> out = find_lift(x);
            add(pos[out.first], 1);
            mark[out.first] = true;
            printf("%d\n", out.second);
        }

        if (debug) {
            printf("sum : ");
            for (int i=1; i<=n; i++) printf("%d ", sum(i));
            printf("\n");
        }
    }

    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf(" %d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf(" %d", &p[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf(" %d %d", &op, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
ballmachine.cpp:97:35: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |             printf("%d\n", ord[idx]);
      |                                   ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 89 ms 11324 KB Output is correct
3 Correct 69 ms 11280 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2664 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 2 ms 2792 KB Output is correct
8 Correct 2 ms 2796 KB Output is correct
9 Correct 7 ms 3192 KB Output is correct
10 Correct 18 ms 4784 KB Output is correct
11 Correct 86 ms 11304 KB Output is correct
12 Correct 61 ms 11316 KB Output is correct
13 Correct 77 ms 11336 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6744 KB Output is correct
2 Correct 146 ms 18028 KB Output is correct
3 Correct 81 ms 14784 KB Output is correct
4 Correct 59 ms 7920 KB Output is correct
5 Correct 57 ms 7720 KB Output is correct
6 Correct 55 ms 7748 KB Output is correct
7 Correct 52 ms 7180 KB Output is correct
8 Correct 34 ms 6724 KB Output is correct
9 Correct 122 ms 18488 KB Output is correct
10 Correct 142 ms 18068 KB Output is correct
11 Correct 121 ms 18084 KB Output is correct
12 Correct 149 ms 16612 KB Output is correct
13 Correct 111 ms 19520 KB Output is correct
14 Correct 79 ms 14884 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10688 KB Output is correct
2 Correct 159 ms 17076 KB Output is correct
3 Correct 120 ms 17856 KB Output is correct
4 Correct 97 ms 15228 KB Output is correct
5 Correct 115 ms 15032 KB Output is correct
6 Correct 109 ms 15076 KB Output is correct
7 Correct 92 ms 13928 KB Output is correct
8 Correct 122 ms 17772 KB Output is correct
9 Correct 149 ms 18664 KB Output is correct
10 Correct 143 ms 18172 KB Output is correct
11 Correct 152 ms 18228 KB Output is correct
12 Correct 151 ms 17188 KB Output is correct
13 Correct 196 ms 21928 KB Output is correct
14 Correct 103 ms 15272 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 18764 KB Output is correct
2 Correct 150 ms 17092 KB Output is correct
3 Correct 108 ms 21524 KB Output is correct
4 Correct 170 ms 18784 KB Output is correct
5 Correct 148 ms 18228 KB Output is correct
6 Correct 162 ms 18112 KB Output is correct
7 Correct 138 ms 16976 KB Output is correct
8 Correct 120 ms 21580 KB Output is correct
9 Correct 84 ms 14824 KB Output is correct