oj.uz

Submission #65118

# Submission time Handle Problem Language Result Execution time Memory
65118 2018-08-06T16:56:34 Z SpeedOfMagic Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 563 ms 34312 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 6 ms 2808 KB Output isn't correct
2 Incorrect 392 ms 19088 KB Output isn't correct
3 Incorrect 313 ms 19264 KB Output isn't correct
4 Incorrect 6 ms 19264 KB Output isn't correct
5 Incorrect 6 ms 19264 KB Output isn't correct
6 Incorrect 6 ms 19264 KB Output isn't correct
7 Incorrect 8 ms 19264 KB Output isn't correct
8 Incorrect 8 ms 19264 KB Output isn't correct
9 Incorrect 28 ms 19264 KB Output isn't correct
10 Incorrect 86 ms 19264 KB Output isn't correct
11 Incorrect 389 ms 19264 KB Output isn't correct
12 Incorrect 292 ms 19520 KB Output isn't correct
13 Incorrect 373 ms 19520 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 19520 KB Output is correct
2 Incorrect 496 ms 30732 KB Output isn't correct
3 Incorrect 286 ms 30732 KB Output isn't correct
4 Incorrect 287 ms 30732 KB Output isn't correct
5 Incorrect 282 ms 30732 KB Output isn't correct
6 Incorrect 313 ms 30732 KB Output isn't correct
7 Incorrect 273 ms 30732 KB Output isn't correct
8 Correct 182 ms 30732 KB Output is correct
9 Incorrect 439 ms 31064 KB Output isn't correct
10 Incorrect 507 ms 31064 KB Output isn't correct
11 Incorrect 398 ms 31064 KB Output isn't correct
12 Incorrect 498 ms 31064 KB Output isn't correct
13 Correct 337 ms 31064 KB Output is correct
14 Incorrect 280 ms 31064 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 196 ms 31064 KB Output isn't correct
2 Incorrect 552 ms 31064 KB Output isn't correct
3 Correct 312 ms 31064 KB Output is correct
4 Incorrect 309 ms 31064 KB Output isn't correct
5 Incorrect 311 ms 31064 KB Output isn't correct
6 Incorrect 316 ms 31064 KB Output isn't correct
7 Incorrect 311 ms 31064 KB Output isn't correct
8 Correct 327 ms 31064 KB Output is correct
9 Incorrect 498 ms 31096 KB Output isn't correct
10 Incorrect 513 ms 31096 KB Output isn't correct
11 Incorrect 533 ms 31096 KB Output isn't correct
12 Incorrect 563 ms 31096 KB Output isn't correct
13 Correct 526 ms 34312 KB Output is correct
14 Incorrect 479 ms 34312 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 477 ms 34312 KB Output isn't correct
2 Incorrect 541 ms 34312 KB Output isn't correct
3 Correct 355 ms 34312 KB Output is correct
4 Incorrect 445 ms 34312 KB Output isn't correct
5 Incorrect 513 ms 34312 KB Output isn't correct
6 Incorrect 460 ms 34312 KB Output isn't correct
7 Incorrect 535 ms 34312 KB Output isn't correct
8 Correct 404 ms 34312 KB Output is correct
9 Incorrect 338 ms 34312 KB Output isn't correct