oj.uz

Submission #959478

# Submission time Handle Problem Language Result Execution time Memory
959478 2024-04-08T09:37:23 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 394 ms 35388 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

int n, q, N;
int cl[maxn], vt[maxn], cha[maxn][18];
int Min[maxn], a[maxn];
vector<int> edges[maxn];
set<int> S;

void pre_dfs(int u, int par) {
    for(int v : edges[u]) if(v != par) {
        pre_dfs(v, u);
        Min[u] = min(Min[u], Min[v]);
    }
}

int In[maxn], Out[maxn], Time;
void dfs(int u, int par) {
    for(int v : edges[u]) if(v != par) {
        cha[v][0] = u; fi(i, 1, 17) cha[v][i] = cha[cha[v][i - 1]][i - 1];
        dfs(v, u);
    }
    a[++N] = u, vt[u] = N;
}

int Add(int k, int ans = 0) {
    while(k--) {
        ans = a[*S.begin()];
        cl[a[*S.begin()]] = 1, S.erase(S.begin());
    }
    return ans;
}

int Del(int u, int ans = 0) {
    fid(i, 17, 0) if(cl[cha[u][i]]) u = cha[u][i], ans += (1 << i);
    S.insert(vt[u]), cl[u] = 0;
    return ans;
}

int main()
{

    cin >> n >> q;

    int rt = 0;
    fi(i, 1, n) {
        Min[i] = i, S.insert(i);
        int x; cin >> x;
        if(x == 0) rt = i;
        else edges[x].push_back(i);
    }

    pre_dfs(rt, 0);
    fi(i, 1, n) sort(all(edges[i]), [](int x, int y) { return Min[x] < Min[y]; } );
    dfs(rt, 0);

    fi(i, 1, q) {
        int type, x; cin >> type >> x;
        if(type == 1) cout << Add(x) << '\n';
        else cout << Del(x) << '\n';
    }

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 244 ms 19248 KB Output is correct
3 Correct 197 ms 19268 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 4 ms 10588 KB Output is correct
8 Correct 4 ms 10588 KB Output is correct
9 Correct 17 ms 11228 KB Output is correct
10 Correct 51 ms 13660 KB Output is correct
11 Correct 223 ms 19352 KB Output is correct
12 Correct 192 ms 19172 KB Output is correct
13 Correct 210 ms 19280 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 15700 KB Output is correct
2 Correct 351 ms 30152 KB Output is correct
3 Correct 211 ms 25060 KB Output is correct
4 Correct 173 ms 16264 KB Output is correct
5 Correct 207 ms 16288 KB Output is correct
6 Correct 170 ms 15980 KB Output is correct
7 Correct 159 ms 14676 KB Output is correct
8 Correct 142 ms 16260 KB Output is correct
9 Correct 256 ms 30288 KB Output is correct
10 Correct 285 ms 29812 KB Output is correct
11 Correct 299 ms 29924 KB Output is correct
12 Correct 263 ms 27744 KB Output is correct
13 Correct 241 ms 31076 KB Output is correct
14 Correct 208 ms 25036 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 20564 KB Output is correct
2 Correct 324 ms 28004 KB Output is correct
3 Correct 214 ms 29776 KB Output is correct
4 Correct 197 ms 25936 KB Output is correct
5 Correct 236 ms 25672 KB Output is correct
6 Correct 182 ms 25684 KB Output is correct
7 Correct 225 ms 24240 KB Output is correct
8 Correct 245 ms 29780 KB Output is correct
9 Correct 310 ms 30544 KB Output is correct
10 Correct 322 ms 30148 KB Output is correct
11 Correct 314 ms 29952 KB Output is correct
12 Correct 394 ms 28424 KB Output is correct
13 Correct 328 ms 35388 KB Output is correct
14 Correct 384 ms 25480 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 30548 KB Output is correct
2 Correct 354 ms 28500 KB Output is correct
3 Correct 257 ms 34900 KB Output is correct
4 Correct 292 ms 31108 KB Output is correct
5 Correct 294 ms 30164 KB Output is correct
6 Correct 268 ms 29972 KB Output is correct
7 Correct 305 ms 28124 KB Output is correct
8 Correct 261 ms 34900 KB Output is correct
9 Correct 208 ms 25116 KB Output is correct