oj.uz

답안 #107308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107308 2019-04-23T08:53:46 Z forestryks Ball Machine (BOI13_ballmachine) C++14
22.4969 / 100
 1000 ms 47608 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 = 1e6 + 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 23928 KB Output isn't correct
2 Incorrect 251 ms 34064 KB Output isn't correct
3 Correct 135 ms 34296 KB Output is correct
4 Execution timed out 1080 ms 23808 KB Time limit exceeded
5 Incorrect 25 ms 23936 KB Output isn't correct
6 Incorrect 31 ms 23932 KB Output isn't correct
7 Execution timed out 1076 ms 23936 KB Time limit exceeded
8 Incorrect 24 ms 24064 KB Output isn't correct
9 Incorrect 38 ms 24448 KB Output isn't correct
10 Incorrect 59 ms 26488 KB Output isn't correct
11 Incorrect 295 ms 34200 KB Output isn't correct
12 Correct 166 ms 34304 KB Output is correct
13 Incorrect 206 ms 34168 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 28396 KB Output is correct
2 Incorrect 345 ms 42980 KB Output isn't correct
3 Correct 163 ms 39064 KB Output is correct
4 Incorrect 129 ms 29944 KB Output isn't correct
5 Incorrect 127 ms 29688 KB Output isn't correct
6 Incorrect 107 ms 29816 KB Output isn't correct
7 Incorrect 130 ms 28792 KB Output isn't correct
8 Correct 67 ms 28328 KB Output is correct
9 Incorrect 319 ms 43332 KB Output isn't correct
10 Incorrect 347 ms 43060 KB Output isn't correct
11 Incorrect 286 ms 43072 KB Output isn't correct
12 Incorrect 344 ms 41080 KB Output isn't correct
13 Correct 213 ms 44768 KB Output is correct
14 Correct 151 ms 39156 KB Output is correct

Subtask #3
5.71428571429 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 148 ms 33656 KB Output isn't correct
2 Incorrect 362 ms 41664 KB Output isn't correct
3 Correct 226 ms 42744 KB Output is correct
4 Incorrect 236 ms 39548 KB Output isn't correct
5 Incorrect 253 ms 39288 KB Output isn't correct
6 Incorrect 248 ms 39208 KB Output isn't correct
7 Incorrect 221 ms 37880 KB Output isn't correct
8 Correct 242 ms 42744 KB Output is correct
9 Incorrect 402 ms 43768 KB Output isn't correct
10 Incorrect 410 ms 43180 KB Output isn't correct
11 Incorrect 398 ms 43208 KB Output isn't correct
12 Incorrect 426 ms 41460 KB Output isn't correct
13 Incorrect 402 ms 47608 KB Output isn't correct
14 Incorrect 299 ms 39284 KB Output isn't correct

Subtask #4
2.22222222222 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 339 ms 43600 KB Output isn't correct
2 Incorrect 370 ms 41564 KB Output isn't correct
3 Correct 263 ms 47364 KB Output is correct
4 Incorrect 384 ms 43716 KB Output isn't correct
5 Incorrect 339 ms 43084 KB Output isn't correct
6 Correct 283 ms 43216 KB Output is correct
7 Incorrect 389 ms 41572 KB Output isn't correct
8 Correct 255 ms 47480 KB Output is correct
9 Correct 164 ms 39156 KB Output is correct