oj.uz

답안 #525522

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525522 2022-02-11T21:04:54 Z crap_the_coder Ball Machine (BOI13_ballmachine) C++17
20.9524 / 100
 1000 ms 37500 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'

const int MOD = 1e9 + 7;
const int INF = LLONG_MAX >> 1;

const int LOG = 25;

signed main() {
    ios::sync_with_stdio(false); cin.tie(NULL);

    int n, q; cin >> n >> q;
    vector<int> tree[n+1];
    int par[n+1][LOG], cd[n+1]{};

    for (int i = 1; i <= n; i++) {
        int c; cin >> c; cd[c]++;
        tree[c].push_back(i);
        tree[i].push_back(c);
    }

    set<int> lf;
    for (int i = 1; i <= n; i++)
        if (cd[i] == 0)
            lf.insert(i);

    function<void(int, int)> dfs = [&](int u, int p) {
        par[u][0] = p;
        for (int i = 1; i < LOG; i++)
            par[u][i] = par[par[u][i-1]][i-1];

        for (auto v : tree[u])
            if (v != p)
                dfs(v, u);

    }; dfs(0, 0);

    bool marked[n+1]{};

    // Queries
    while (q--) {
        int t, k; cin >> t >> k;

        if (t == 1) {
            int ans = 0;
            while (k--) {
                marked[ans = *lf.begin()] = true;

                lf.erase(lf.begin());
                if (--cd[par[ans][0]] == 0)
                    lf.insert(par[ans][0]);
            }

            cout << ans << endl;

        } else {
            int r = 0;
            for (int j = LOG-1; j >= 0; j--)
                if (marked[par[k][j]])
                    k = par[k][j], r += (1 << j);

            cout << r << endl;

            marked[k] = false; cd[par[k][0]]++;
            lf.insert(k); lf.erase(par[k][0]);
        }
    }
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1063 ms 308 KB Time limit exceeded
2 Execution timed out 1080 ms 20804 KB Time limit exceeded
3 Incorrect 71 ms 20932 KB Output isn't correct
4 Execution timed out 1085 ms 204 KB Time limit exceeded
5 Execution timed out 1067 ms 324 KB Time limit exceeded
6 Incorrect 1 ms 588 KB Output isn't correct
7 Execution timed out 1076 ms 568 KB Time limit exceeded
8 Execution timed out 1088 ms 588 KB Time limit exceeded
9 Execution timed out 1089 ms 1484 KB Time limit exceeded
10 Execution timed out 1095 ms 5324 KB Time limit exceeded
11 Execution timed out 1072 ms 20532 KB Time limit exceeded
12 Incorrect 72 ms 20932 KB Output isn't correct
13 Incorrect 113 ms 20856 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 7480 KB Output is correct
2 Execution timed out 1036 ms 33928 KB Time limit exceeded
3 Correct 90 ms 30764 KB Output is correct
4 Execution timed out 1076 ms 10552 KB Time limit exceeded
5 Execution timed out 1074 ms 10432 KB Time limit exceeded
6 Execution timed out 1074 ms 10564 KB Time limit exceeded
7 Execution timed out 1072 ms 9156 KB Time limit exceeded
8 Correct 30 ms 7428 KB Output is correct
9 Execution timed out 1101 ms 33512 KB Time limit exceeded
10 Execution timed out 1085 ms 33964 KB Time limit exceeded
11 Execution timed out 1089 ms 34244 KB Time limit exceeded
12 Execution timed out 1078 ms 31416 KB Time limit exceeded
13 Correct 118 ms 32784 KB Output is correct
14 Correct 99 ms 30704 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 79 ms 17092 KB Output isn't correct
2 Incorrect 198 ms 32384 KB Output isn't correct
3 Correct 133 ms 29708 KB Output is correct
4 Incorrect 120 ms 26972 KB Output isn't correct
5 Incorrect 132 ms 27640 KB Output isn't correct
6 Incorrect 135 ms 27556 KB Output isn't correct
7 Incorrect 134 ms 25684 KB Output isn't correct
8 Correct 131 ms 29636 KB Output is correct
9 Incorrect 202 ms 34012 KB Output isn't correct
10 Incorrect 207 ms 34852 KB Output isn't correct
11 Incorrect 200 ms 34828 KB Output isn't correct
12 Incorrect 193 ms 32368 KB Output isn't correct
13 Correct 196 ms 37500 KB Output is correct
14 Incorrect 153 ms 31164 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1012 ms 33120 KB Time limit exceeded
2 Incorrect 202 ms 32324 KB Output isn't correct
3 Correct 127 ms 37008 KB Output is correct
4 Execution timed out 1088 ms 33076 KB Time limit exceeded
5 Execution timed out 1055 ms 34392 KB Time limit exceeded
6 Execution timed out 1032 ms 34628 KB Time limit exceeded
7 Incorrect 185 ms 32316 KB Output isn't correct
8 Correct 126 ms 37080 KB Output is correct
9 Correct 97 ms 30872 KB Output is correct