oj.uz

Submission #447657

# Submission time Handle Problem Language Result Execution time Memory
447657 2021-07-27T08:56:38 Z prvocislo Ball Machine (BOI13_ballmachine) C++17
100 / 100
 228 ms 26668 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5, logn = 17;
int l[logn][maxn], mini[maxn], inv[maxn], n, q;
vector<pair<int, int> > g[maxn];
vector<int> ord;
void dfs1(int u, int p = -1)
{
    for (int i = 1; i < logn; i++) if (l[i-1][u] != -1) l[i][u] = l[i-1][l[i-1][u]];
    for (pair<int, int> &v : g[u]) if (v.first != p) 
    {
        l[0][v.first] = u;
        dfs1(v.first, u);
        v.second = mini[v.first];
        mini[u] = min(mini[u], mini[v.first]);
    }
}
void dfs2(int u, int p = -1)
{
    for (pair<int, int> &v : g[u]) if (v.first != p) 
        dfs2(v.first, u);
    inv[u] = ord.size(), ord.push_back(u);
}
bool cmp(pair<int, int> a, pair<int, int> b) { return a.second < b.second; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    iota(mini, mini+n, 0);
    int root = -1;
    for (int i = 0, p; i < n; i++)
    {
        cin >> p; p--;
        if (p == -1) root = i;
        else g[p].push_back({i, -1});
    }
    for (int i = 0; i < logn; i++) for (int j = 0; j < n; j++) l[i][j] = -1;
    dfs1(root); 
    for (int i = 0; i < n; i++) sort(g[i].begin(), g[i].end(), cmp);
    dfs2(root);
    set<int> s;
    for (int i = 0; i < n; i++) s.insert(i);
    vector<bool> b(n, false);
    while (q--)
    {
        int typ; cin >> typ;
        if (typ == 1)
        {
           int k; cin >> k;
           int ans = -1;
           for (int i = 0; i < k; i++)
           {
                int vr = ord[*s.begin()];
                ans = vr;
                b[vr] = true;
                s.erase(s.begin());
           }
           cout << ans+1 << "\n";
        }
        else
        {
            int x; cin >> x; x--;
            int y = x, ans = 0;
            for (int i = logn-1; i >= 0; i--) if (l[i][y] != -1 && b[l[i][y]]) y = l[i][y], ans += (1 << i);
            b[y] = false; s.insert(inv[y]);
            cout << ans << "\n";
        }
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 140 ms 12152 KB Output is correct
3 Correct 88 ms 12284 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 8 ms 3336 KB Output is correct
10 Correct 25 ms 5092 KB Output is correct
11 Correct 154 ms 12364 KB Output is correct
12 Correct 76 ms 12260 KB Output is correct
13 Correct 115 ms 12160 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7280 KB Output is correct
2 Correct 211 ms 21312 KB Output is correct
3 Correct 104 ms 16968 KB Output is correct
4 Correct 79 ms 8692 KB Output is correct
5 Correct 71 ms 8820 KB Output is correct
6 Correct 71 ms 8356 KB Output is correct
7 Correct 69 ms 7364 KB Output is correct
8 Correct 39 ms 7220 KB Output is correct
9 Correct 179 ms 21780 KB Output is correct
10 Correct 216 ms 21440 KB Output is correct
11 Correct 162 ms 21308 KB Output is correct
12 Correct 180 ms 19060 KB Output is correct
13 Correct 129 ms 23856 KB Output is correct
14 Correct 106 ms 16968 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 12356 KB Output is correct
2 Correct 212 ms 19584 KB Output is correct
3 Correct 157 ms 21828 KB Output is correct
4 Correct 136 ms 18072 KB Output is correct
5 Correct 129 ms 17764 KB Output is correct
6 Correct 133 ms 17724 KB Output is correct
7 Correct 158 ms 16124 KB Output is correct
8 Correct 142 ms 21832 KB Output is correct
9 Correct 212 ms 21976 KB Output is correct
10 Correct 199 ms 21508 KB Output is correct
11 Correct 228 ms 21436 KB Output is correct
12 Correct 202 ms 19532 KB Output is correct
13 Correct 211 ms 26668 KB Output is correct
14 Correct 184 ms 16936 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 22136 KB Output is correct
2 Correct 218 ms 19584 KB Output is correct
3 Correct 143 ms 26464 KB Output is correct
4 Correct 213 ms 21984 KB Output is correct
5 Correct 220 ms 21548 KB Output is correct
6 Correct 182 ms 21396 KB Output is correct
7 Correct 207 ms 19556 KB Output is correct
8 Correct 149 ms 26444 KB Output is correct
9 Correct 102 ms 16960 KB Output is correct