oj.uz

Submission #964258

# Submission time Handle Problem Language Result Execution time Memory
964258 2024-04-16T13:48:13 Z Pring Ball Machine (BOI13_ballmachine) C++17
7.53968 / 100
 1000 ms 34020 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, rt, 0);
    // FOR(i, 0, n) cout << scr[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) 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 Execution timed out 1053 ms 13148 KB Time limit exceeded
2 Execution timed out 1047 ms 20764 KB Time limit exceeded
3 Incorrect 57 ms 20876 KB Output isn't correct
4 Execution timed out 1076 ms 13404 KB Time limit exceeded
5 Execution timed out 1070 ms 13148 KB Time limit exceeded
6 Incorrect 3 ms 13208 KB Output isn't correct
7 Execution timed out 1041 ms 13148 KB Time limit exceeded
8 Execution timed out 1081 ms 13148 KB Time limit exceeded
9 Incorrect 11 ms 13660 KB Output isn't correct
10 Execution timed out 1064 ms 15068 KB Time limit exceeded
11 Incorrect 120 ms 20728 KB Output isn't correct
12 Incorrect 56 ms 20732 KB Output isn't correct
13 Incorrect 90 ms 20848 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17488 KB Output is correct
2 Incorrect 151 ms 28548 KB Output isn't correct
3 Incorrect 63 ms 23912 KB Output isn't correct
4 Execution timed out 1032 ms 18260 KB Time limit exceeded
5 Execution timed out 1042 ms 17744 KB Time limit exceeded
6 Incorrect 73 ms 18224 KB Output isn't correct
7 Incorrect 69 ms 17488 KB Output isn't correct
8 Correct 35 ms 17400 KB Output is correct
9 Incorrect 141 ms 29008 KB Output isn't correct
10 Incorrect 138 ms 28692 KB Output isn't correct
11 Incorrect 114 ms 28576 KB Output isn't correct
12 Incorrect 159 ms 26500 KB Output isn't correct
13 Correct 72 ms 31312 KB Output is correct
14 Incorrect 62 ms 24004 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 21164 KB Output isn't correct
2 Incorrect 194 ms 27072 KB Output isn't correct
3 Incorrect 79 ms 29448 KB Output isn't correct
4 Incorrect 82 ms 25828 KB Output isn't correct
5 Incorrect 85 ms 25428 KB Output isn't correct
6 Incorrect 96 ms 25428 KB Output isn't correct
7 Incorrect 107 ms 23892 KB Output isn't correct
8 Incorrect 77 ms 29520 KB Output isn't correct
9 Incorrect 192 ms 29132 KB Output isn't correct
10 Incorrect 171 ms 28744 KB Output isn't correct
11 Incorrect 149 ms 28812 KB Output isn't correct
12 Incorrect 136 ms 26808 KB Output isn't correct
13 Incorrect 114 ms 34020 KB Output isn't correct
14 Incorrect 168 ms 24292 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 29216 KB Output isn't correct
2 Incorrect 198 ms 26728 KB Output isn't correct
3 Correct 79 ms 33660 KB Output is correct
4 Incorrect 125 ms 29216 KB Output isn't correct
5 Incorrect 133 ms 28644 KB Output isn't correct
6 Incorrect 122 ms 28784 KB Output isn't correct
7 Incorrect 149 ms 26668 KB Output isn't correct
8 Correct 91 ms 33604 KB Output is correct
9 Incorrect 79 ms 23880 KB Output isn't correct