oj.uz

Submission #107305

# Submission time Handle Problem Language Result Execution time Memory
107305 2019-04-23T08:45:09 Z forestryks Ball Machine (BOI13_ballmachine) C++14
22.4969 / 100
 1000 ms 26488 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 = 19; 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 221 ms 13108 KB Output isn't correct
3 Correct 136 ms 13160 KB Output is correct
4 Execution timed out 1061 ms 2688 KB Time limit exceeded
5 Incorrect 5 ms 2816 KB Output isn't correct
6 Incorrect 5 ms 2944 KB Output isn't correct
7 Execution timed out 1077 ms 2944 KB Time limit exceeded
8 Incorrect 6 ms 2816 KB Output isn't correct
9 Incorrect 13 ms 3328 KB Output isn't correct
10 Incorrect 44 ms 5368 KB Output isn't correct
11 Incorrect 241 ms 13176 KB Output isn't correct
12 Correct 128 ms 13048 KB Output is correct
13 Incorrect 179 ms 12920 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 7284 KB Output is correct
2 Incorrect 348 ms 21920 KB Output isn't correct
3 Correct 163 ms 17952 KB Output is correct
4 Incorrect 127 ms 8796 KB Output isn't correct
5 Incorrect 138 ms 8568 KB Output isn't correct
6 Incorrect 108 ms 8644 KB Output isn't correct
7 Incorrect 123 ms 7660 KB Output isn't correct
8 Correct 56 ms 7288 KB Output is correct
9 Incorrect 276 ms 22284 KB Output isn't correct
10 Incorrect 347 ms 21952 KB Output isn't correct
11 Incorrect 283 ms 21712 KB Output isn't correct
12 Incorrect 324 ms 19960 KB Output isn't correct
13 Correct 202 ms 23544 KB Output is correct
14 Correct 153 ms 18012 KB Output is correct

Subtask #3
5.71428571429 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 12628 KB Output isn't correct
2 Incorrect 382 ms 20304 KB Output isn't correct
3 Correct 238 ms 21596 KB Output is correct
4 Incorrect 242 ms 18436 KB Output isn't correct
5 Incorrect 242 ms 18040 KB Output isn't correct
6 Incorrect 247 ms 18100 KB Output isn't correct
7 Incorrect 240 ms 16892 KB Output isn't correct
8 Correct 265 ms 21720 KB Output is correct
9 Incorrect 382 ms 22472 KB Output isn't correct
10 Incorrect 378 ms 22072 KB Output isn't correct
11 Incorrect 407 ms 21960 KB Output isn't correct
12 Incorrect 386 ms 20412 KB Output isn't correct
13 Incorrect 337 ms 26488 KB Output isn't correct
14 Incorrect 290 ms 18172 KB Output isn't correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 375 ms 22564 KB Output isn't correct
2 Incorrect 328 ms 20524 KB Output isn't correct
3 Correct 271 ms 26200 KB Output is correct
4 Incorrect 365 ms 22492 KB Output isn't correct
5 Incorrect 378 ms 22108 KB Output isn't correct
6 Correct 293 ms 21884 KB Output is correct
7 Incorrect 384 ms 20600 KB Output isn't correct
8 Correct 260 ms 26316 KB Output is correct
9 Correct 159 ms 18136 KB Output is correct