oj.uz

Submission #65117

# Submission time Handle Problem Language Result Execution time Memory
65117 2018-08-06T16:55:53 Z SpeedOfMagic Ball Machine (BOI13_ballmachine) C++14
0 / 100
 797 ms 81124 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];

int tim[N];
int timCur = 1;
set<pair<int, int>> nxt;
void dfs(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])
        dfs(i, cur);

    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;

    //printVar(r);
    dfs(r, -1);
    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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2936 KB Output isn't correct
2 Incorrect 553 ms 21224 KB Output isn't correct
3 Incorrect 422 ms 22236 KB Output isn't correct
4 Incorrect 5 ms 22236 KB Output isn't correct
5 Incorrect 8 ms 22236 KB Output isn't correct
6 Incorrect 9 ms 22236 KB Output isn't correct
7 Incorrect 10 ms 22236 KB Output isn't correct
8 Incorrect 13 ms 22236 KB Output isn't correct
9 Incorrect 38 ms 22236 KB Output isn't correct
10 Incorrect 114 ms 22236 KB Output isn't correct
11 Incorrect 556 ms 23632 KB Output isn't correct
12 Incorrect 480 ms 24872 KB Output isn't correct
13 Incorrect 466 ms 25724 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 227 ms 25724 KB Output isn't correct
2 Incorrect 730 ms 39532 KB Output isn't correct
3 Incorrect 567 ms 39532 KB Output isn't correct
4 Incorrect 310 ms 39532 KB Output isn't correct
5 Incorrect 382 ms 39532 KB Output isn't correct
6 Incorrect 341 ms 39532 KB Output isn't correct
7 Incorrect 337 ms 39532 KB Output isn't correct
8 Incorrect 264 ms 39532 KB Output isn't correct
9 Incorrect 631 ms 45868 KB Output isn't correct
10 Incorrect 666 ms 46956 KB Output isn't correct
11 Incorrect 679 ms 48052 KB Output isn't correct
12 Incorrect 656 ms 48052 KB Output isn't correct
13 Incorrect 528 ms 50492 KB Output isn't correct
14 Incorrect 488 ms 50492 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 354 ms 50492 KB Output isn't correct
2 Incorrect 724 ms 52312 KB Output isn't correct
3 Incorrect 481 ms 52312 KB Output isn't correct
4 Incorrect 489 ms 52312 KB Output isn't correct
5 Incorrect 504 ms 52312 KB Output isn't correct
6 Incorrect 568 ms 52312 KB Output isn't correct
7 Incorrect 514 ms 52312 KB Output isn't correct
8 Incorrect 479 ms 56068 KB Output isn't correct
9 Incorrect 739 ms 60996 KB Output isn't correct
10 Incorrect 781 ms 61892 KB Output isn't correct
11 Incorrect 748 ms 63264 KB Output isn't correct
12 Incorrect 797 ms 63436 KB Output isn't correct
13 Incorrect 719 ms 69464 KB Output isn't correct
14 Incorrect 676 ms 69464 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 690 ms 69464 KB Output isn't correct
2 Incorrect 734 ms 69464 KB Output isn't correct
3 Incorrect 595 ms 74408 KB Output isn't correct
4 Incorrect 730 ms 74408 KB Output isn't correct
5 Incorrect 711 ms 74408 KB Output isn't correct
6 Incorrect 607 ms 75248 KB Output isn't correct
7 Incorrect 725 ms 75252 KB Output isn't correct
8 Incorrect 555 ms 81124 KB Output isn't correct
9 Incorrect 520 ms 81124 KB Output isn't correct