oj.uz

답안 #467877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467877 2021-08-25T08:04:26 Z JasperL Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 384 ms 21952 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define maxn 100005
#define maxh 20

int n, q, rt;
vector<int> e[maxn];
int jump[maxn][maxh];
vector<int> pos;
int idx[maxn];
priority_queue<pair<int,int>> pq;

bool ball[maxn];

void dfs(int i) {
    for (int j : e[i]) dfs(j);
    pos.push_back(i);
}

void add() {
    auto z = pq.top(); pq.pop();
    int i = z.second;
    ball[i] = true;
    //cout << i + 1 << endl;
}

int rem(int i) {
    int z = 0;
    for (int j = maxh-1; j >= 0; j--) {
        if (jump[i][j] == -1 || ball[jump[i][j]] == false) continue;
        z += (1<<j); i = jump[i][j];
    }
    ball[i] = false;
    pq.push({-idx[i],i});
    return z;
}

int main() {
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> jump[i][0]; jump[i][0]--;
        if (jump[i][0] != -1) e[jump[i][0]].push_back(i);
        else rt = i;
    }
    for (int i = 0; i < n; i++) sort(e[i].begin(),e[i].end());
    for (int j = 1; j < maxh; j++) {
        for (int i = 0; i < n; i++) {
            if (jump[i][j-1] == -1) jump[i][j] = -1;
            else jump[i][j] = jump[jump[i][j-1]][j-1];
        }
    }
    dfs(rt);
    //for (int j : pos) cout << j+1 << " ";
    //cout << endl;
    for (int i = 0; i < n; i++) idx[pos[i]] = i;
    for (int i = 0; i < n; i++) {
        pq.push({-idx[i],i});
    }
    for (int i = 0; i < q; i++) {
        int t; cin >> t;
        if (t == 1) {
            int sz; cin >> sz;
            for (int j = 0; j < sz-1; j++) add();
            int j = pq.top().second;
            cout << j + 1 << endl;
            add();
        } else {
            int j; cin >> j; j--;
            int res = rem(j);
            cout << res << endl;
        }
    }
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 301 ms 11332 KB Output isn't correct
3 Incorrect 294 ms 11372 KB Output isn't correct
4 Incorrect 2 ms 2664 KB Output isn't correct
5 Incorrect 2 ms 2636 KB Output isn't correct
6 Incorrect 3 ms 2728 KB Output isn't correct
7 Incorrect 4 ms 2764 KB Output isn't correct
8 Incorrect 5 ms 2764 KB Output isn't correct
9 Incorrect 22 ms 3148 KB Output isn't correct
10 Incorrect 58 ms 4852 KB Output isn't correct
11 Incorrect 285 ms 11520 KB Output isn't correct
12 Incorrect 262 ms 11292 KB Output isn't correct
13 Incorrect 287 ms 11400 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 6848 KB Output is correct
2 Incorrect 334 ms 18052 KB Output isn't correct
3 Incorrect 293 ms 14868 KB Output isn't correct
4 Incorrect 209 ms 7912 KB Output isn't correct
5 Incorrect 209 ms 7804 KB Output isn't correct
6 Incorrect 210 ms 7864 KB Output isn't correct
7 Incorrect 211 ms 7060 KB Output isn't correct
8 Correct 191 ms 6644 KB Output is correct
9 Incorrect 330 ms 18524 KB Output isn't correct
10 Incorrect 326 ms 17984 KB Output isn't correct
11 Incorrect 324 ms 18092 KB Output isn't correct
12 Incorrect 324 ms 16572 KB Output isn't correct
13 Correct 299 ms 19516 KB Output is correct
14 Incorrect 282 ms 14980 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 166 ms 10688 KB Output isn't correct
2 Incorrect 349 ms 17024 KB Output isn't correct
3 Correct 227 ms 17856 KB Output is correct
4 Incorrect 216 ms 15304 KB Output isn't correct
5 Incorrect 219 ms 14864 KB Output isn't correct
6 Incorrect 217 ms 14896 KB Output isn't correct
7 Incorrect 214 ms 13876 KB Output isn't correct
8 Correct 238 ms 17812 KB Output is correct
9 Incorrect 334 ms 18616 KB Output isn't correct
10 Incorrect 342 ms 18276 KB Output isn't correct
11 Incorrect 344 ms 18372 KB Output isn't correct
12 Incorrect 364 ms 17052 KB Output isn't correct
13 Correct 384 ms 21952 KB Output is correct
14 Incorrect 309 ms 15188 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 335 ms 18612 KB Output isn't correct
2 Incorrect 346 ms 17212 KB Output isn't correct
3 Correct 308 ms 21552 KB Output is correct
4 Incorrect 344 ms 18552 KB Output isn't correct
5 Incorrect 352 ms 18128 KB Output isn't correct
6 Incorrect 343 ms 18188 KB Output isn't correct
7 Incorrect 330 ms 16956 KB Output isn't correct
8 Correct 296 ms 21552 KB Output is correct
9 Incorrect 280 ms 14784 KB Output isn't correct