oj.uz

Submission #65140

# Submission time Handle Problem Language Result Execution time Memory
65140 2018-08-06T17:32:53 Z SpeedOfMagic Ball Machine (BOI13_ballmachine) C++17
100 / 100
 622 ms 39724 KB 
/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
#define printVar(a) put #a << ": " << a << endl;
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here
const int N = 1e5 + 1;
vint g[N];

const int M = 20;
int kthAncestor[N][M];

void calcAncestor(int cur, int par) {
    kthAncestor[cur][0] = par;
    int p = par;
    int k = 0;
    while (p != -1) {
        p = kthAncestor[p][k];
        k++;
        kthAncestor[cur][k] = p;
    }

    for (int i : g[cur])
        calcAncestor(i, cur);
}

int minInTree[N];

void calcMin(int cur) {
    minInTree[cur] = cur;
    for (int i : g[cur]) {
        calcMin(i);
        minInTree[cur] = min(minInTree[cur], minInTree[i]);
    }
}

int timCur = 1;
int tim[N];
set<pair<int, int>> nxt;
void calcOrder(int cur) {
    v<pair<int, int>> ord;
    for (int i : g[cur])
        ord.pb({minInTree[i], i});
    sort(ord.begin(), ord.end());

    for (auto i : ord)
        calcOrder(i.second);
    tim[cur] = timCur++;
    nxt.insert({tim[cur], cur});
}

bool hasBall[N];
void run() {
    int n, q;
    read(n, q);
    n++;
    int r = -1;
    rep(i, 1, n) {
        int p;
        get p;
        if (p == 0)
            r = i;
        else
            g[p].pb(i);
    }

    rep(i, 1, n)
        rep(j, 0, M)
            kthAncestor[i][j] = -1;
    calcAncestor(r, -1);
    calcMin(r);
    calcOrder(r);

    //for (auto i : nxt) debug(i.first, i.second);
    memset(&hasBall, 0, sizeof(hasBall));
    for (; q; q--) {
        int t;
        get t;
        if (t == 1) {
            int k;
            get k;
            while (k) {
                auto d = *nxt.begin();
                nxt.erase(d);
                hasBall[d.second] = 1;
                k--;
                if (k == 0)
                    put d.second;
            }
        } else {
            int v;
            get v;
            int cur = v;
            int d = 0;
            for (int i = M - 1; i >= 0;) {
                if (!hasBall[kthAncestor[cur][i]])
                    i--;
                else {
                    cur = kthAncestor[cur][i];
                    d += (1 << i);
                }
            }
            hasBall[cur] = 0;
            nxt.insert({tim[cur], cur});

            put d;
        }

        eol;
    }
}

int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2808 KB Output is correct
2 Correct 410 ms 19560 KB Output is correct
3 Correct 300 ms 19756 KB Output is correct
4 Correct 5 ms 19756 KB Output is correct
5 Correct 4 ms 19756 KB Output is correct
6 Correct 7 ms 19756 KB Output is correct
7 Correct 7 ms 19756 KB Output is correct
8 Correct 9 ms 19756 KB Output is correct
9 Correct 29 ms 19756 KB Output is correct
10 Correct 80 ms 19756 KB Output is correct
11 Correct 441 ms 19756 KB Output is correct
12 Correct 304 ms 19900 KB Output is correct
13 Correct 390 ms 19900 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 19900 KB Output is correct
2 Correct 606 ms 33720 KB Output is correct
3 Correct 324 ms 33720 KB Output is correct
4 Correct 320 ms 33720 KB Output is correct
5 Correct 332 ms 33720 KB Output is correct
6 Correct 293 ms 33720 KB Output is correct
7 Correct 302 ms 33720 KB Output is correct
8 Correct 203 ms 33720 KB Output is correct
9 Correct 478 ms 34160 KB Output is correct
10 Correct 529 ms 34160 KB Output is correct
11 Correct 485 ms 34160 KB Output is correct
12 Correct 513 ms 34160 KB Output is correct
13 Correct 444 ms 35372 KB Output is correct
14 Correct 389 ms 35372 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 35372 KB Output is correct
2 Correct 622 ms 35372 KB Output is correct
3 Correct 379 ms 35372 KB Output is correct
4 Correct 363 ms 35372 KB Output is correct
5 Correct 353 ms 35372 KB Output is correct
6 Correct 342 ms 35372 KB Output is correct
7 Correct 358 ms 35372 KB Output is correct
8 Correct 393 ms 35372 KB Output is correct
9 Correct 585 ms 35372 KB Output is correct
10 Correct 597 ms 35372 KB Output is correct
11 Correct 581 ms 35372 KB Output is correct
12 Correct 598 ms 35372 KB Output is correct
13 Correct 545 ms 39724 KB Output is correct
14 Correct 500 ms 39724 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 39724 KB Output is correct
2 Correct 539 ms 39724 KB Output is correct
3 Correct 431 ms 39724 KB Output is correct
4 Correct 499 ms 39724 KB Output is correct
5 Correct 515 ms 39724 KB Output is correct
6 Correct 434 ms 39724 KB Output is correct
7 Correct 575 ms 39724 KB Output is correct
8 Correct 404 ms 39724 KB Output is correct
9 Correct 331 ms 39724 KB Output is correct