oj.uz

답안 #559765

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559765 2022-05-10T14:24:42 Z hoanghq2004 Ball Machine (BOI13_ballmachine) C++14
0 / 100
 117 ms 15668 KB 
#include <bits/stdc++.h>

using namespace std;

int n, q;
vector <int> e[100010];
int ti, pos[100010], ord[100010];
int minc[100010];

void dfs1(int u) {
    minc[u] = n + 1;
    for (auto v: e[u]) {
        dfs1(v);
        if (minc[v] < minc[u]) {
            minc[u] = minc[v];
        }
    }
    minc[u] = min(minc[u], u);
}

void dfs2(int u) {
    ord[ti] = u;
    pos[u] = ti--;
    for (auto v: e[u]) dfs2(v);
}

int st[400010];

void update(int id, int l, int r, int i, int val) {
    if (i > r || i < l) return;
    if (l == r) {
        st[id] = 1;
        return;
    }
    int mid = l + r >> 1;
    update(id * 2, l, mid, i, val);
    update(id * 2 + 1, mid + 1, r, i, val);
    st[id] = min(st[id * 2], st[id * 2 + 1]);
}

int get(int id, int l, int r) {
    if (l == r) return l;
    int mid = l + r >> 1;
    if (st[id * 2] == 0) return get(id * 2, l, mid);
    else return get(id * 2 + 1, mid + 1, r);
}

int cmp(int u, int v) {
    return minc[u] > minc[v];
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        int p;
        scanf("%d", &p);
        e[p].push_back(i);
    }
    ti = n;
    dfs1(e[0].front());
    for (int u = 1; u <= n; ++u)
        sort(e[u].begin(), e[u].end(), cmp);
    dfs2(e[0].front());
//    for (int i = 1; i <= n; ++i) cout << ord[i] << " ";
    while (q--) {
        int c, k;
        scanf("%d%d", &c, &k);
        if (c == 1) {
            int ans = 0;
            while (k--) {
                ans = get(1, 1, n);
                update(1, 1, n, ans, 1);
            }
            cout << ord[ans] << "\n";
        }
        else {
            update(1, 1, n, k, 0);
            cout << "0\n";
        }
    }
}

Compilation message

ballmachine.cpp: In function 'void update(int, int, int, int, int)':
ballmachine.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = l + r >> 1;
      |               ~~^~~
ballmachine.cpp: In function 'int get(int, int, int)':
ballmachine.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = l + r >> 1;
      |               ~~^~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d", &p);
      |         ~~~~~^~~~~~~~~~
ballmachine.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d%d", &c, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Incorrect 75 ms 6268 KB Output isn't correct
3 Incorrect 55 ms 6200 KB Output isn't correct
4 Incorrect 2 ms 2656 KB Output isn't correct
5 Incorrect 2 ms 2644 KB Output isn't correct
6 Incorrect 2 ms 2644 KB Output isn't correct
7 Incorrect 3 ms 2644 KB Output isn't correct
8 Incorrect 2 ms 2644 KB Output isn't correct
9 Incorrect 6 ms 2804 KB Output isn't correct
10 Incorrect 18 ms 3412 KB Output isn't correct
11 Incorrect 74 ms 6184 KB Output isn't correct
12 Incorrect 56 ms 6096 KB Output isn't correct
13 Incorrect 73 ms 6184 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 5548 KB Output isn't correct
2 Incorrect 103 ms 11348 KB Output isn't correct
3 Incorrect 66 ms 7024 KB Output isn't correct
4 Incorrect 57 ms 5708 KB Output isn't correct
5 Incorrect 54 ms 5708 KB Output isn't correct
6 Incorrect 50 ms 5696 KB Output isn't correct
7 Incorrect 51 ms 5096 KB Output isn't correct
8 Incorrect 35 ms 5580 KB Output isn't correct
9 Incorrect 96 ms 11892 KB Output isn't correct
10 Incorrect 93 ms 11348 KB Output isn't correct
11 Incorrect 94 ms 11364 KB Output isn't correct
12 Incorrect 90 ms 9676 KB Output isn't correct
13 Incorrect 72 ms 13996 KB Output isn't correct
14 Incorrect 71 ms 7048 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 7224 KB Output isn't correct
2 Incorrect 94 ms 9792 KB Output isn't correct
3 Incorrect 62 ms 13068 KB Output isn't correct
4 Incorrect 60 ms 10036 KB Output isn't correct
5 Incorrect 61 ms 9668 KB Output isn't correct
6 Incorrect 63 ms 9720 KB Output isn't correct
7 Incorrect 59 ms 8396 KB Output isn't correct
8 Incorrect 67 ms 13076 KB Output isn't correct
9 Incorrect 92 ms 11836 KB Output isn't correct
10 Incorrect 92 ms 11452 KB Output isn't correct
11 Incorrect 90 ms 11588 KB Output isn't correct
12 Incorrect 90 ms 9800 KB Output isn't correct
13 Incorrect 98 ms 15668 KB Output isn't correct
14 Incorrect 85 ms 7752 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 99 ms 11988 KB Output isn't correct
2 Incorrect 96 ms 9888 KB Output isn't correct
3 Incorrect 78 ms 15240 KB Output isn't correct
4 Incorrect 117 ms 12000 KB Output isn't correct
5 Incorrect 91 ms 11440 KB Output isn't correct
6 Incorrect 97 ms 11452 KB Output isn't correct
7 Incorrect 91 ms 9872 KB Output isn't correct
8 Incorrect 82 ms 15316 KB Output isn't correct
9 Incorrect 68 ms 7060 KB Output isn't correct