oj.uz

Submission #107304

# Submission time Handle Problem Language Result Execution time Memory
107304 2019-04-23T08:43:33 Z forestryks Ball Machine (BOI13_ballmachine) C++14
21.9414 / 100
 1000 ms 27080 KB 
///////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout)
#define f first
#define s second
#define x1 x1qwer
#define y1 y1qwer
#define right right123
#define left left123
#define foreach(it, v) for (auto it : v)
#define rep(it, n) for (int it = 0; it < n; ++it)
#define forin(it, l, r) for (int it = l; it < r; ++it)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double DINF = numeric_limits<double>::infinity();
const ll MOD = 1e9 + 7;
const double EPS = 1e-7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
mt19937 mmtw_(MOD);
uniform_int_distribution<ll> rd_;
ll randomll() { return rd_(mmtw_);}
ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; }
////////////////////////////////////////////////////////////////////////////////////////////////

const int MAXN = 1e5 + 5;
int n, q;
vector<int> g[MAXN];
int root;
int up[MAXN][20];
set<pair<int, int>> s;
int mn[MAXN];
int tin[MAXN];
bool used[MAXN];
int h[MAXN];

void dfsm(int v) {
    mn[v] = v;
    for (auto to : g[v]) {
        h[to] = h[v] + 1;
        dfsm(to);
        mn[v] = min(mn[v], mn[to]);
    }

    sort(all(g[v]), [&](int a, int b){
        return mn[a] < mn[b];
    });
}

int tt = 0;
void dfs(int v) {
    for (int i = 1; i < 20; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (auto to : g[v]) {
        dfs(to);
    }
    tin[v] = tt++;
}

int main() {
    FAST_IO;
    cin >> n >> q;
    rep(i, n) {
        int p;
        cin >> p;
        p--;
        if (p == -1) {
            root = i;
        } else {
            g[p].push_back(i);
            up[i][0] = p;
        }
    }

    dfsm(root);
    dfs(root);

    rep(i, n) {
        s.insert({tin[i], i});
    }

    // for (auto &it : s) {
    //     cout << it.f << ' ' << it.s << endl;
    // }

    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int k, r = -1;
            cin >> k;
            rep(j, k) {
                used[s.begin()->s] = true;
                r = s.begin()->s;
                s.erase(s.begin());
            }

            cout << r + 1 << '\n';
        } else {
            int v, r = 0;
            cin >> v;
            v--;
            int w = v;
            for (int i = 20; i >= 0; --i) {
                if (used[up[v][i]]) {
                    v = up[v][i];
                }
            }
            used[v] = false;
            s.insert({tin[v], v});
            cout << h[w] - h[v] << '\n';
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:110:20: warning: unused variable 'r' [-Wunused-variable]
             int v, r = 0;
                    ^

Subtask #1
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2688 KB Output isn't correct
2 Incorrect 243 ms 13660 KB Output isn't correct
3 Correct 122 ms 13816 KB Output is correct
4 Execution timed out 1075 ms 2688 KB Time limit exceeded
5 Incorrect 4 ms 2688 KB Output isn't correct
6 Incorrect 4 ms 2816 KB Output isn't correct
7 Incorrect 5 ms 2816 KB Output isn't correct
8 Incorrect 6 ms 2944 KB Output isn't correct
9 Incorrect 15 ms 3456 KB Output isn't correct
10 Incorrect 35 ms 5496 KB Output isn't correct
11 Incorrect 275 ms 13720 KB Output isn't correct
12 Correct 119 ms 13816 KB Output is correct
13 Incorrect 164 ms 13584 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7800 KB Output is correct
2 Incorrect 347 ms 22648 KB Output isn't correct
3 Correct 129 ms 18676 KB Output is correct
4 Execution timed out 1072 ms 9396 KB Time limit exceeded
5 Incorrect 94 ms 9336 KB Output isn't correct
6 Incorrect 83 ms 9324 KB Output isn't correct
7 Incorrect 129 ms 8440 KB Output isn't correct
8 Correct 45 ms 7800 KB Output is correct
9 Incorrect 329 ms 22904 KB Output isn't correct
10 Incorrect 349 ms 22528 KB Output isn't correct
11 Incorrect 271 ms 22532 KB Output isn't correct
12 Incorrect 352 ms 20556 KB Output isn't correct
13 Correct 205 ms 24184 KB Output is correct
14 Correct 132 ms 18548 KB Output is correct

Subtask #3
5.71428571429 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 13228 KB Output isn't correct
2 Incorrect 394 ms 21164 KB Output isn't correct
3 Correct 227 ms 22264 KB Output is correct
4 Incorrect 238 ms 19148 KB Output isn't correct
5 Incorrect 208 ms 18680 KB Output isn't correct
6 Incorrect 264 ms 18808 KB Output isn't correct
7 Incorrect 240 ms 17400 KB Output isn't correct
8 Correct 207 ms 22208 KB Output is correct
9 Incorrect 383 ms 23116 KB Output isn't correct
10 Incorrect 361 ms 22676 KB Output isn't correct
11 Incorrect 375 ms 22700 KB Output isn't correct
12 Incorrect 419 ms 21172 KB Output isn't correct
13 Incorrect 364 ms 27080 KB Output isn't correct
14 Incorrect 292 ms 18776 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 350 ms 23284 KB Output isn't correct
2 Incorrect 391 ms 21088 KB Output isn't correct
3 Correct 234 ms 27052 KB Output is correct
4 Incorrect 337 ms 23252 KB Output isn't correct
5 Incorrect 348 ms 22784 KB Output isn't correct
6 Incorrect 228 ms 22648 KB Output isn't correct
7 Incorrect 329 ms 21156 KB Output isn't correct
8 Correct 215 ms 26872 KB Output is correct
9 Correct 140 ms 18676 KB Output is correct