oj.uz

Submission #445258

# Submission time Handle Problem Language Result Execution time Memory
445258 2021-07-17T07:36:17 Z cpp219 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 433 ms 24368 KB 
#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll Log2 = 20;
const ll inf = 1e18 + 7;

priority_queue<LL,vector<LL>,greater<LL>> pq;
vector<ll> g[N];
ll n,Q,root,x,mn[N],par[N][Log2],d[N],last,type,take[N],pos[N];
ll nTime = 1;

void DFS(ll u){
    for (ll i = 1;i < Log2;i++) if ((1 << i) <= d[u])
        par[u][i] = par[par[u][i - 1]][i - 1];
    mn[u] = u;
    for (auto i : g[u]){
        par[i][0] = u; d[i] = d[u] + 1; DFS(i);
        mn[u] = min(mn[u],mn[i]);
    }
}

bool lf(ll x,ll y){
    return mn[x] < mn[y];
}

void geiDFS(ll u){
    sort(g[u].begin(),g[u].end(),lf);
    for (auto i : g[u]) geiDFS(i);
    pos[u] = nTime; nTime++;
}

ll Jump(ll node,ll step){
    for (ll i = Log2 - 1;i >= 0;i--){
        if (step >= (1 << i)){
            node = par[node][i]; step -= (1 << i);
        }
    }
    return node;
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n>>Q;
    for (ll i = 1;i <= n;i++){
        cin>>x;
        if (x == 0) root = i;
        else g[x].push_back(i);
    }
    DFS(root); geiDFS(root);
    for (ll i = 1;i <= n;i++) pq.push({pos[i],i});
    while(Q--){
        cin>>type>>x;
        if (type == 1){
            while(x--){
                LL t = pq.top(); pq.pop();
                last = t.sc; take[t.sc] = 1;
            }
            cout<<last<<"\n";
        }
        else{
            ll l,m,h; l = 0; h = d[x];
            while(l <= h){
                m = (l + h)/2; ll nxt = Jump(x,m);
                if (!take[nxt]) h = m - 1;
                else l = m + 1;
            }
            ll cur = Jump(x,h); last = cur;
            cout<<h<<"\n"; take[cur] = 0; pq.push({pos[cur],cur});
        }
    }
}

Compilation message

ballmachine.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
ballmachine.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
ballmachine.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
ballmachine.cpp:14:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const ll inf = 1e18 + 7;
      |                ~~~~~^~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 110 ms 10616 KB Output is correct
3 Correct 70 ms 10580 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 8 ms 3148 KB Output is correct
10 Correct 21 ms 4756 KB Output is correct
11 Correct 113 ms 10640 KB Output is correct
12 Correct 69 ms 10560 KB Output is correct
13 Correct 99 ms 10644 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6772 KB Output is correct
2 Correct 316 ms 19024 KB Output is correct
3 Correct 78 ms 14232 KB Output is correct
4 Correct 101 ms 7796 KB Output is correct
5 Correct 138 ms 7860 KB Output is correct
6 Correct 133 ms 7760 KB Output is correct
7 Correct 113 ms 6856 KB Output is correct
8 Correct 57 ms 6848 KB Output is correct
9 Correct 262 ms 19476 KB Output is correct
10 Correct 313 ms 19000 KB Output is correct
11 Correct 290 ms 19004 KB Output is correct
12 Correct 277 ms 16796 KB Output is correct
13 Correct 144 ms 21424 KB Output is correct
14 Correct 80 ms 14268 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 11260 KB Output is correct
2 Correct 337 ms 17216 KB Output is correct
3 Correct 255 ms 20060 KB Output is correct
4 Correct 192 ms 16224 KB Output is correct
5 Correct 235 ms 15772 KB Output is correct
6 Correct 229 ms 15816 KB Output is correct
7 Correct 197 ms 14364 KB Output is correct
8 Correct 230 ms 20004 KB Output is correct
9 Correct 273 ms 19512 KB Output is correct
10 Correct 371 ms 19164 KB Output is correct
11 Correct 433 ms 19200 KB Output is correct
12 Correct 367 ms 17208 KB Output is correct
13 Correct 398 ms 24368 KB Output is correct
14 Correct 111 ms 14648 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 19708 KB Output is correct
2 Correct 375 ms 17228 KB Output is correct
3 Correct 168 ms 23832 KB Output is correct
4 Correct 326 ms 19792 KB Output is correct
5 Correct 390 ms 19284 KB Output is correct
6 Correct 276 ms 19128 KB Output is correct
7 Correct 335 ms 17368 KB Output is correct
8 Correct 154 ms 23900 KB Output is correct
9 Correct 80 ms 14300 KB Output is correct