oj.uz

Submission #480314

# Submission time Handle Problem Language Result Execution time Memory
480314 2021-10-15T15:46:16 Z Lobo Ball Machine (BOI13_ballmachine) C++17
100 / 100
 663 ms 29988 KB 
#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 110000

ii n, q, a[maxn], mn[maxn], ant[maxn], timer, p[maxn][25], h[maxn];
vector<ii> g[maxn];

bool cmp(ii a, ii b) {
    return mn[a] < mn[b];
}

void dfsmn(ii u, ii ant) {
    //cout << u << " " << ant << endl;
    p[u][0] = ant;
    //cout << u << " " << 0 << " = " << p[u][0] << endl;

    for(ii i = 1; i <= 20; i++) {
        p[u][i] = p[p[u][i-1]][i-1];
        //cout << u << " " << i << " = " << p[u][i] << endl;
    }

    for(auto v : g[u]) {
        h[v] = h[u]+1;
        dfsmn(v,u);
        mn[u] = min(mn[u],mn[v]);
    }
}

void dfs(ii u, ii ant) {
    for(auto v : g[u]) {
        dfs(v,u);
    }

    a[u] = ++timer;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    cin >> n >> q;

    ii root;
    for(ii i = 1; i <= n; i++) {
        mn[i] = i;
        ii v;
        cin >> v;

        if(v == 0) root = i;
        else g[v].pb(i);
    }

    dfsmn(root,root);

    for(ii i = 1; i <= n; i++) {
        sort(all(g[i]),cmp);
    }

    dfs(root,root);

    set<pair<ii,ii>> s;
    for(ii i = 1; i <= n; i++) {
        s.insert(mp(a[i],i));
    }


    for(ii i = 1; i <= q; i++) {
        ii op;
        cin >> op;
        if(op == 1) {
            ii k; cin >> k;

            ii ans;
            while(k--) {
                ans = s.begin()->sc;
                s.erase(*s.begin());
            }

            cout << ans << endl;
        }
        else {
            ii u; cin >> u;
            ii ans = h[u];
            for(ii i = 20; i >= 0; i--) {
                ii v = p[u][i];
                if(s.find(mp(a[v],v)) == s.end()) {
                    u = v;
                }
            }

            ans-= h[u];

            s.insert(mp(a[u],u));
            cout << ans << endl;
        }
    }
    

}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:10:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   10 | #define endl '\n'
      |              ^~~~
ballmachine.cpp:89:16: note: 'ans' was declared here
   89 |             ii ans;
      |                ^~~
ballmachine.cpp:75:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |     dfs(root,root);
      |     ~~~^~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2892 KB Output is correct
2 Correct 226 ms 14372 KB Output is correct
3 Correct 111 ms 14632 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 3 ms 3020 KB Output is correct
8 Correct 4 ms 3020 KB Output is correct
9 Correct 12 ms 3532 KB Output is correct
10 Correct 37 ms 5708 KB Output is correct
11 Correct 205 ms 14280 KB Output is correct
12 Correct 108 ms 14664 KB Output is correct
13 Correct 184 ms 14444 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 7932 KB Output is correct
2 Correct 505 ms 24560 KB Output is correct
3 Correct 162 ms 20024 KB Output is correct
4 Correct 162 ms 9632 KB Output is correct
5 Correct 241 ms 9520 KB Output is correct
6 Correct 211 ms 9492 KB Output is correct
7 Correct 211 ms 8376 KB Output is correct
8 Correct 72 ms 8304 KB Output is correct
9 Correct 419 ms 25028 KB Output is correct
10 Correct 501 ms 24616 KB Output is correct
11 Correct 373 ms 24540 KB Output is correct
12 Correct 448 ms 22240 KB Output is correct
13 Correct 175 ms 26688 KB Output is correct
14 Correct 205 ms 20072 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 14020 KB Output is correct
2 Correct 530 ms 22800 KB Output is correct
3 Correct 319 ms 24504 KB Output is correct
4 Correct 245 ms 20676 KB Output is correct
5 Correct 366 ms 20404 KB Output is correct
6 Correct 310 ms 20264 KB Output is correct
7 Correct 337 ms 18844 KB Output is correct
8 Correct 286 ms 24404 KB Output is correct
9 Correct 406 ms 25196 KB Output is correct
10 Correct 534 ms 24788 KB Output is correct
11 Correct 526 ms 24884 KB Output is correct
12 Correct 499 ms 22796 KB Output is correct
13 Correct 464 ms 29988 KB Output is correct
14 Correct 238 ms 20212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 25240 KB Output is correct
2 Correct 481 ms 22864 KB Output is correct
3 Correct 276 ms 29828 KB Output is correct
4 Correct 416 ms 25196 KB Output is correct
5 Correct 663 ms 24724 KB Output is correct
6 Correct 471 ms 24696 KB Output is correct
7 Correct 525 ms 22732 KB Output is correct
8 Correct 220 ms 29860 KB Output is correct
9 Correct 171 ms 20100 KB Output is correct