oj.uz

Submission #964273

# Submission time Handle Problem Language Result Execution time Memory
964273 2024-04-16T14:09:15 Z Pring Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 150 ms 20812 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 100005, LG = 18;
int n, q, rt;
vector<int> chd[MXN];
int d[MXN], dfn[MXN], scr[MXN], C;
int p[LG][MXN];
bitset<MXN> b;
// set<int> S;
priority_queue<int, vector<int>, greater<int>> pq;

void DFS(int id, int par, int dep) {
    p[0][id] = par;
    d[id] = dep;
    for (auto &i : chd[id]) {
        DFS(i, id, dep + 1);
    }
    scr[C] = id;
    dfn[id] = C++;
}

int calc1(int x) {
    int ans = 0;
    while (x--) {
        assert(pq.size());
        // int id = *S.begin();
        // S.erase(S.begin());
        int id = pq.top();
        pq.pop();
        b[scr[id]] = true;
        ans = scr[id];
    }
    return ans;
}

int calc2(int x) {
    int x0 = x;
    for (int w = LG - 1; w >= 0; w--) {
        if (!b[p[w][x]]) continue;
        x = p[w][x];
    }
    b[x] = false;
    // S.insert(dfn[x]);
    pq.push(dfn[x]);
    return d[x0] - d[x];
}

void miku() {
    int x, y;
    cin >> n >> q;
    FOR(i, 1, n + 1) {
        cin >> x;
        if (x == 0) rt = i;
        else chd[x].push_back(i);
    }
    DFS(rt, 0, 0);
    // FOR(i, 1, n + 1) cout << dfn[i] << ' ';
    // cout << endl;
    FOR(w, 1, LG) {
        FOR(i, 1, n + 1) p[w][i] = p[w - 1][p[w - 1][i]];
    }
    FOR(i, 0, n) pq.push(i);
    while (q--) {
        cin >> x >> y;
        if (x == 1) cout << calc1(y) << '\n';
        else cout << calc2(y) << '\n';
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10840 KB Output isn't correct
2 Incorrect 90 ms 13620 KB Output isn't correct
3 Incorrect 37 ms 13516 KB Output isn't correct
4 Incorrect 2 ms 10840 KB Output isn't correct
5 Incorrect 2 ms 10840 KB Output isn't correct
6 Incorrect 3 ms 10844 KB Output isn't correct
7 Incorrect 3 ms 11100 KB Output isn't correct
8 Incorrect 2 ms 10844 KB Output isn't correct
9 Incorrect 6 ms 10844 KB Output isn't correct
10 Incorrect 15 ms 11356 KB Output isn't correct
11 Incorrect 78 ms 13632 KB Output isn't correct
12 Incorrect 34 ms 13544 KB Output isn't correct
13 Incorrect 65 ms 13392 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13240 KB Output is correct
2 Incorrect 84 ms 17028 KB Output isn't correct
3 Incorrect 43 ms 13928 KB Output isn't correct
4 Incorrect 53 ms 13392 KB Output isn't correct
5 Incorrect 51 ms 13420 KB Output isn't correct
6 Incorrect 54 ms 13152 KB Output isn't correct
7 Incorrect 53 ms 12716 KB Output isn't correct
8 Correct 26 ms 13396 KB Output is correct
9 Incorrect 95 ms 17484 KB Output isn't correct
10 Incorrect 150 ms 17068 KB Output isn't correct
11 Incorrect 84 ms 17012 KB Output isn't correct
12 Incorrect 100 ms 15956 KB Output isn't correct
13 Correct 47 ms 19556 KB Output is correct
14 Incorrect 46 ms 14124 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 14152 KB Output isn't correct
2 Incorrect 112 ms 16052 KB Output isn't correct
3 Correct 54 ms 18648 KB Output is correct
4 Incorrect 50 ms 16084 KB Output isn't correct
5 Incorrect 112 ms 15764 KB Output isn't correct
6 Incorrect 53 ms 15884 KB Output isn't correct
7 Incorrect 62 ms 14808 KB Output isn't correct
8 Correct 55 ms 18644 KB Output is correct
9 Incorrect 93 ms 17612 KB Output isn't correct
10 Incorrect 106 ms 17104 KB Output isn't correct
11 Incorrect 106 ms 17104 KB Output isn't correct
12 Incorrect 94 ms 16236 KB Output isn't correct
13 Correct 130 ms 20812 KB Output is correct
14 Incorrect 75 ms 14160 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 17448 KB Output isn't correct
2 Incorrect 92 ms 16000 KB Output isn't correct
3 Correct 46 ms 20356 KB Output is correct
4 Incorrect 98 ms 17484 KB Output isn't correct
5 Incorrect 137 ms 17108 KB Output isn't correct
6 Incorrect 94 ms 16868 KB Output isn't correct
7 Incorrect 96 ms 15848 KB Output isn't correct
8 Correct 56 ms 20508 KB Output is correct
9 Incorrect 37 ms 14024 KB Output isn't correct