oj.uz

Submission #964266

# Submission time Handle Problem Language Result Execution time Memory
964266 2024-04-16T13:58:19 Z Pring Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 177 ms 39300 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> edge[MXN];
vector<int> chd[MXN];
int d[MXN], dfn[MXN], scr[MXN], C;
int p[LG][MXN];
bitset<MXN> b;
set<int> S;

void DFS(int id, int par, int dep) {
    p[0][id] = par;
    d[id] = dep;
    for (auto &i : edge[id]) {
        if (i == par) continue;
        chd[id].push_back(i);
    }
    sort(chd[id].begin(), chd[id].end());
    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(S.size());
        int id = *S.begin();
        S.erase(S.begin());
        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]);
    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 {
            edge[i].push_back(x);
            edge[x].push_back(i);
        }
    }
    DFS(rt, 0, 0);
    FOR(w, 1, LG) {
        FOR(i, 1, n + 1) p[w][i] = p[w - 1][p[w - 1][i]];
    }
    FOR(i, 0, n) S.insert(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 2 ms 13148 KB Output isn't correct
2 Runtime error 100 ms 39300 KB Execution killed with signal 6
3 Incorrect 52 ms 19776 KB Output isn't correct
4 Runtime error 16 ms 26460 KB Execution killed with signal 6
5 Incorrect 2 ms 13148 KB Output isn't correct
6 Incorrect 4 ms 13148 KB Output isn't correct
7 Runtime error 15 ms 26716 KB Execution killed with signal 6
8 Runtime error 13 ms 26716 KB Execution killed with signal 6
9 Incorrect 8 ms 13400 KB Output isn't correct
10 Runtime error 33 ms 29724 KB Execution killed with signal 6
11 Incorrect 118 ms 19600 KB Output isn't correct
12 Incorrect 51 ms 19764 KB Output isn't correct
13 Incorrect 106 ms 19576 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16916 KB Output is correct
2 Incorrect 177 ms 27304 KB Output isn't correct
3 Incorrect 62 ms 22864 KB Output isn't correct
4 Runtime error 52 ms 35408 KB Execution killed with signal 6
5 Runtime error 29 ms 34976 KB Execution killed with signal 6
6 Incorrect 62 ms 17500 KB Output isn't correct
7 Incorrect 67 ms 16724 KB Output isn't correct
8 Correct 28 ms 16828 KB Output is correct
9 Incorrect 135 ms 27736 KB Output isn't correct
10 Incorrect 141 ms 27408 KB Output isn't correct
11 Incorrect 126 ms 27356 KB Output isn't correct
12 Incorrect 143 ms 25168 KB Output isn't correct
13 Correct 71 ms 30288 KB Output is correct
14 Incorrect 61 ms 23064 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 20564 KB Output isn't correct
2 Incorrect 137 ms 25436 KB Output isn't correct
3 Correct 96 ms 28612 KB Output is correct
4 Incorrect 83 ms 24800 KB Output isn't correct
5 Incorrect 97 ms 24528 KB Output isn't correct
6 Incorrect 91 ms 24464 KB Output isn't correct
7 Incorrect 82 ms 22900 KB Output isn't correct
8 Correct 93 ms 28500 KB Output is correct
9 Incorrect 132 ms 27732 KB Output isn't correct
10 Incorrect 160 ms 27392 KB Output isn't correct
11 Incorrect 135 ms 27220 KB Output isn't correct
12 Incorrect 146 ms 25428 KB Output isn't correct
13 Correct 124 ms 32596 KB Output is correct
14 Incorrect 134 ms 22824 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 27856 KB Output isn't correct
2 Incorrect 153 ms 25288 KB Output isn't correct
3 Correct 84 ms 32392 KB Output is correct
4 Incorrect 155 ms 27800 KB Output isn't correct
5 Incorrect 145 ms 27220 KB Output isn't correct
6 Incorrect 112 ms 27364 KB Output isn't correct
7 Incorrect 159 ms 25208 KB Output isn't correct
8 Correct 74 ms 32336 KB Output is correct
9 Incorrect 66 ms 22816 KB Output isn't correct