oj.uz

Submission #959476

# Submission time Handle Problem Language Result Execution time Memory
959476 2024-04-08T09:35:48 Z Neco_arc Ball Machine (BOI13_ballmachine) C++17
100 / 100
 310 ms 35408 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 219 ms 19256 KB Output is correct
3 Correct 186 ms 19284 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 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 6 ms 10840 KB Output is correct
9 Correct 17 ms 10964 KB Output is correct
10 Correct 45 ms 13660 KB Output is correct
11 Correct 238 ms 19216 KB Output is correct
12 Correct 192 ms 19556 KB Output is correct
13 Correct 242 ms 19144 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 15836 KB Output is correct
2 Correct 289 ms 30196 KB Output is correct
3 Correct 206 ms 25036 KB Output is correct
4 Correct 170 ms 16392 KB Output is correct
5 Correct 178 ms 16104 KB Output is correct
6 Correct 169 ms 16032 KB Output is correct
7 Correct 155 ms 14548 KB Output is correct
8 Correct 148 ms 15864 KB Output is correct
9 Correct 279 ms 30408 KB Output is correct
10 Correct 300 ms 29968 KB Output is correct
11 Correct 256 ms 29780 KB Output is correct
12 Correct 260 ms 27788 KB Output is correct
13 Correct 275 ms 31052 KB Output is correct
14 Correct 230 ms 25036 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 20560 KB Output is correct
2 Correct 308 ms 28184 KB Output is correct
3 Correct 194 ms 29776 KB Output is correct
4 Correct 193 ms 26136 KB Output is correct
5 Correct 194 ms 25684 KB Output is correct
6 Correct 180 ms 25760 KB Output is correct
7 Correct 181 ms 24196 KB Output is correct
8 Correct 194 ms 29740 KB Output is correct
9 Correct 304 ms 30616 KB Output is correct
10 Correct 287 ms 30032 KB Output is correct
11 Correct 290 ms 30156 KB Output is correct
12 Correct 306 ms 28112 KB Output is correct
13 Correct 310 ms 35408 KB Output is correct
14 Correct 271 ms 25640 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 30680 KB Output is correct
2 Correct 286 ms 28536 KB Output is correct
3 Correct 243 ms 34880 KB Output is correct
4 Correct 279 ms 30548 KB Output is correct
5 Correct 298 ms 30480 KB Output is correct
6 Correct 267 ms 30116 KB Output is correct
7 Correct 301 ms 28552 KB Output is correct
8 Correct 247 ms 34712 KB Output is correct
9 Correct 205 ms 25336 KB Output is correct