oj.uz

Submission #445240

# Submission time Handle Problem Language Result Execution time Memory
445240 2021-07-17T04:29:05 Z cpp219 Ball Machine (BOI13_ballmachine) C++14
8.68742 / 100
 1000 ms 53496 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[N];
vector<ll> g[N];
ll n,Q,root,x,mn[N],par[N][Log2],d[N],last,type,take[N];

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]); pq[u].push({mn[i],i});
    }
}

void Add(ll u){
    if (pq[u].empty()){
        take[u] = 1; last = u;
        pq[par[u][0]].pop();
        return;
    }
    LL t = pq[u].top(); Add(t.sc);
}

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 "test"
    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); last = root;
    while(Q--){
        cin>>type>>x;
        if (type == 1){
            while(x--){
                //if (take[last]){
                 //   last = par[last][0]; pq[last].pop();
                //}
                //cout<<last; return 0;
                Add(1);
            }
            cout<<last<<"\n";
            //cout<<take[5]; return 0;
        }
        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;
            if (cur != root){
                ll p = par[cur][0]; pq[p].push({mn[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:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 11596 KB Execution killed with signal 6
2 Runtime error 122 ms 30108 KB Execution killed with signal 11
3 Correct 79 ms 13776 KB Output is correct
4 Runtime error 10 ms 11672 KB Execution killed with signal 6
5 Runtime error 9 ms 11628 KB Execution killed with signal 6
6 Incorrect 4 ms 5836 KB Output isn't correct
7 Runtime error 10 ms 11836 KB Execution killed with signal 6
8 Runtime error 9 ms 11824 KB Execution killed with signal 6
9 Runtime error 15 ms 12952 KB Execution killed with signal 6
10 Runtime error 31 ms 16368 KB Execution killed with signal 6
11 Runtime error 132 ms 31288 KB Execution killed with signal 6
12 Correct 76 ms 13892 KB Output is correct
13 Runtime error 116 ms 30432 KB Execution killed with signal 6

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 10624 KB Time limit exceeded
2 Execution timed out 1099 ms 24284 KB Time limit exceeded
3 Correct 82 ms 17480 KB Output is correct
4 Runtime error 113 ms 25304 KB Execution killed with signal 6
5 Runtime error 154 ms 24904 KB Execution killed with signal 6
6 Runtime error 52 ms 23268 KB Execution killed with signal 11
7 Runtime error 127 ms 22336 KB Execution killed with signal 6
8 Execution timed out 1093 ms 10692 KB Time limit exceeded
9 Execution timed out 1093 ms 25240 KB Time limit exceeded
10 Execution timed out 1089 ms 24260 KB Time limit exceeded
11 Incorrect 294 ms 25924 KB Output isn't correct
12 Incorrect 305 ms 22520 KB Output isn't correct
13 Execution timed out 1092 ms 28760 KB Time limit exceeded
14 Correct 80 ms 17468 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 15400 KB Time limit exceeded
2 Execution timed out 1098 ms 21572 KB Time limit exceeded
3 Execution timed out 1099 ms 26756 KB Time limit exceeded
4 Runtime error 208 ms 44784 KB Execution killed with signal 6
5 Runtime error 164 ms 42808 KB Execution killed with signal 6
6 Runtime error 240 ms 43540 KB Execution killed with signal 6
7 Execution timed out 1084 ms 18416 KB Time limit exceeded
8 Execution timed out 1092 ms 26720 KB Time limit exceeded
9 Runtime error 260 ms 53184 KB Execution killed with signal 6
10 Incorrect 552 ms 26052 KB Output isn't correct
11 Execution timed out 1088 ms 24260 KB Time limit exceeded
12 Execution timed out 1088 ms 21560 KB Time limit exceeded
13 Execution timed out 1098 ms 31940 KB Time limit exceeded
14 Runtime error 100 ms 37360 KB Execution killed with signal 11

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 420 ms 53496 KB Execution killed with signal 6
2 Execution timed out 1088 ms 21516 KB Time limit exceeded
3 Execution timed out 1086 ms 31612 KB Time limit exceeded
4 Runtime error 391 ms 53444 KB Execution killed with signal 6
5 Incorrect 393 ms 25996 KB Output isn't correct
6 Execution timed out 1092 ms 24260 KB Time limit exceeded
7 Execution timed out 1095 ms 21572 KB Time limit exceeded
8 Execution timed out 1099 ms 31684 KB Time limit exceeded
9 Correct 74 ms 17468 KB Output is correct