oj.uz

Submission #964265

# Submission time Handle Problem Language Result Execution time Memory
964265 2024-04-16T13:56:30 Z Pring Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 1000 ms 32756 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--) {
        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 6 ms 13144 KB Output isn't correct
2 Execution timed out 1026 ms 19604 KB Time limit exceeded
3 Incorrect 58 ms 19664 KB Output isn't correct
4 Execution timed out 1031 ms 13144 KB Time limit exceeded
5 Incorrect 2 ms 13144 KB Output isn't correct
6 Incorrect 3 ms 13144 KB Output isn't correct
7 Execution timed out 1092 ms 13148 KB Time limit exceeded
8 Execution timed out 1020 ms 13148 KB Time limit exceeded
9 Incorrect 7 ms 13400 KB Output isn't correct
10 Execution timed out 1071 ms 14684 KB Time limit exceeded
11 Incorrect 102 ms 19548 KB Output isn't correct
12 Incorrect 54 ms 19900 KB Output isn't correct
13 Incorrect 96 ms 19724 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16920 KB Output is correct
2 Incorrect 189 ms 27220 KB Output isn't correct
3 Incorrect 82 ms 22860 KB Output isn't correct
4 Execution timed out 1088 ms 17608 KB Time limit exceeded
5 Execution timed out 1060 ms 17244 KB Time limit exceeded
6 Incorrect 71 ms 17752 KB Output isn't correct
7 Incorrect 64 ms 16740 KB Output isn't correct
8 Correct 36 ms 16736 KB Output is correct
9 Incorrect 131 ms 27584 KB Output isn't correct
10 Incorrect 166 ms 27368 KB Output isn't correct
11 Incorrect 135 ms 27356 KB Output isn't correct
12 Incorrect 164 ms 25116 KB Output isn't correct
13 Correct 81 ms 30288 KB Output is correct
14 Incorrect 64 ms 23056 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 20560 KB Output isn't correct
2 Incorrect 153 ms 25424 KB Output isn't correct
3 Correct 83 ms 28484 KB Output is correct
4 Incorrect 81 ms 24912 KB Output isn't correct
5 Incorrect 118 ms 24400 KB Output isn't correct
6 Incorrect 139 ms 24396 KB Output isn't correct
7 Incorrect 104 ms 23168 KB Output isn't correct
8 Correct 84 ms 28512 KB Output is correct
9 Incorrect 196 ms 27732 KB Output isn't correct
10 Incorrect 172 ms 27224 KB Output isn't correct
11 Incorrect 183 ms 27216 KB Output isn't correct
12 Incorrect 171 ms 25676 KB Output isn't correct
13 Correct 162 ms 32756 KB Output is correct
14 Incorrect 204 ms 22928 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 27832 KB Output isn't correct
2 Incorrect 171 ms 25444 KB Output isn't correct
3 Correct 87 ms 32336 KB Output is correct
4 Incorrect 131 ms 27892 KB Output isn't correct
5 Incorrect 154 ms 27412 KB Output isn't correct
6 Incorrect 120 ms 27376 KB Output isn't correct
7 Incorrect 155 ms 25428 KB Output isn't correct
8 Correct 93 ms 32332 KB Output is correct
9 Incorrect 63 ms 22932 KB Output isn't correct