oj.uz

Submission #83248

# Submission time Handle Problem Language Result Execution time Memory
83248 2018-11-06T10:40:59 Z teomrn Ball Machine (BOI13_ballmachine) C++14
100 / 100
 238 ms 28576 KB 
#include <bits/stdc++.h>
#define lsb(x) ((x) & -(x))
using namespace std;

const int NMAX = 100010;
const int LGMAX = 18;

vector <int> adia[NMAX + 10];
bool taken[NMAX + 10];
int tata[NMAX + 10];
int stramos[LGMAX + 1][NMAX + 10];
int vmin[NMAX + 10];
int aib[NMAX + 10];
int poz[NMAX + 10];
int is_on_poz[NMAX + 10], naib, cnt;

void update(int poz, int val)
{
    while (poz <= naib)
        aib[poz] += val, poz += lsb(poz);
}

int first_empty()
{
    int ans = 0, pas = 2 * naib;
    while (pas /= 2)
        if (aib[ans + pas] == pas)
            ans += pas;
    return ans + 1;
}

void dfs(int nod, int tata) {
    vmin[nod] = nod;
    stramos[0][nod] = tata;
    for (int i = 1; i <= LGMAX; i++)
        stramos[i][nod] = stramos[i - 1][stramos[i - 1][nod]];
    for (auto i : adia[nod]) {
        dfs(i, nod);
        vmin[nod] = min(vmin[nod], vmin[i]);
    }
}

void dfs2(int nod)
{
    sort(adia[nod].begin(), adia[nod].end(), [](int a, int b) { return vmin[a] < vmin[b]; });
    for (auto i : adia[nod])
        dfs2(i);
    poz[nod] = ++cnt;
    is_on_poz[cnt] = nod;
}

int add()
{
    int where = first_empty();
    update(where, 1);
    taken[is_on_poz[where]] = 1;
    return is_on_poz[where];
}

int rem(int where)
{
    assert(taken[where]);
    int ans = 0;
    for (int i = LGMAX; i >= 0; i--)
        if (taken[stramos[i][where]])
            ans += (1 << i), where = stramos[i][where];

    taken[where] = 0;
    update(poz[where], -1);
    return ans;
}

int main()
{
    int n, m;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    int root;
    naib = n;
    while (naib != lsb(naib))
        naib += lsb(naib);

    for (int i = 1; i <= n; i++) {
        cin >> tata[i];
        if (tata[i] == 0)
            root = i;
        adia[tata[i]].push_back(i);
    }

    dfs(root, 0);
    dfs2(root);

    while (m--) {
        int type, x;
        cin >> type >> x;

        if (type == 1) {
            int last;
            while (x--)
                last = add();

            cout << last << '\n';
        }
        else
            cout << rem(x) << '\n';
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:103:29: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout << last << '\n';
                             ^~~~
ballmachine.cpp:92:9: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs2(root);
     ~~~~^~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 103 ms 10644 KB Output is correct
3 Correct 109 ms 10644 KB Output is correct
4 Correct 5 ms 10644 KB Output is correct
5 Correct 4 ms 10644 KB Output is correct
6 Correct 5 ms 10644 KB Output is correct
7 Correct 5 ms 10644 KB Output is correct
8 Correct 5 ms 10644 KB Output is correct
9 Correct 9 ms 10644 KB Output is correct
10 Correct 30 ms 10644 KB Output is correct
11 Correct 106 ms 11160 KB Output is correct
12 Correct 89 ms 11316 KB Output is correct
13 Correct 117 ms 11316 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 11316 KB Output is correct
2 Correct 190 ms 19968 KB Output is correct
3 Correct 99 ms 19968 KB Output is correct
4 Correct 59 ms 19968 KB Output is correct
5 Correct 72 ms 19968 KB Output is correct
6 Correct 78 ms 19968 KB Output is correct
7 Correct 62 ms 19968 KB Output is correct
8 Correct 45 ms 19968 KB Output is correct
9 Correct 161 ms 21324 KB Output is correct
10 Correct 165 ms 21404 KB Output is correct
11 Correct 144 ms 21552 KB Output is correct
12 Correct 161 ms 21552 KB Output is correct
13 Correct 132 ms 24856 KB Output is correct
14 Correct 98 ms 24856 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 24856 KB Output is correct
2 Correct 186 ms 24856 KB Output is correct
3 Correct 150 ms 24856 KB Output is correct
4 Correct 119 ms 24856 KB Output is correct
5 Correct 134 ms 24856 KB Output is correct
6 Correct 116 ms 24856 KB Output is correct
7 Correct 114 ms 24856 KB Output is correct
8 Correct 154 ms 24856 KB Output is correct
9 Correct 167 ms 24856 KB Output is correct
10 Correct 182 ms 24856 KB Output is correct
11 Correct 192 ms 24856 KB Output is correct
12 Correct 179 ms 24856 KB Output is correct
13 Correct 238 ms 27688 KB Output is correct
14 Correct 139 ms 27688 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 27688 KB Output is correct
2 Correct 184 ms 27688 KB Output is correct
3 Correct 143 ms 27688 KB Output is correct
4 Correct 197 ms 27688 KB Output is correct
5 Correct 204 ms 27688 KB Output is correct
6 Correct 153 ms 27688 KB Output is correct
7 Correct 177 ms 27688 KB Output is correct
8 Correct 158 ms 28576 KB Output is correct
9 Correct 98 ms 28576 KB Output is correct