oj.uz

Submission #282977

# Submission time Handle Problem Language Result Execution time Memory
282977 2020-08-25T08:07:41 Z Atill83 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 720 ms 31524 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, q;
vector<int> adj[MAXN];
int pri[MAXN];
struct op{
    bool operator()(int a, int b){
        return pri[a] < pri[b];
    }
};

set<int, op> st;
const int LOG = 18;
int par[MAXN][18];
int sbt[MAXN];
int pr = 1;

void dfs1(int v){
    sbt[v] = v;

    for(int j: adj[v]){
        dfs1(j);
        sbt[v] = min(sbt[v], sbt[j]);
    }
    sort(adj[v].begin(), adj[v].end(), [](int a, int b){
        return sbt[a] < sbt[b];
    });
}

bool covered[MAXN];
void dfs2(int v){

    for(int j: adj[v]){
        dfs2(j);
    }
    pri[v] = pr++;
    if(v) st.insert(v);
}

int kpar(int v, int k){
    for(int j = 0; j < LOG; j++){
        if((1<<j) & k){
            v = par[v][j];
        }
    }
    return v;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>q;

    for(int i = 1; i <= n; i++){
        cin>>par[i][0];
        adj[par[i][0]].push_back(i);
    }
    for(int j = 1; j < LOG; j++){
        for(int i = 1; i <= n; i++){
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }

    dfs1(0);
    dfs2(0);

    while(q--){
        int type, num;
        cin>>type>>num;
        if(type == 1){
            int last = 0;
            for(int j = 0; j < num; j++){
                assert(!st.empty());
                int u = *st.begin();
                st.erase(*st.begin());
                covered[u] = 1;
                last = u;
            }
            cout<<last<<endl;
        }else{
            int l = 0, r = n;
            while(l < r){
                int m = (l + r + 1) / 2;
                if(covered[kpar(num, m)]){
                    l = m;
                }else{
                    r = m - 1;
                }
            }
            cout<<l<<endl;
            int u = kpar(num, l);
            covered[u] = 0;
            st.insert(u);
        }
    }

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 186 ms 18024 KB Output is correct
3 Correct 114 ms 18040 KB Output is correct
4 Correct 5 ms 7552 KB Output is correct
5 Correct 5 ms 7424 KB Output is correct
6 Correct 6 ms 7552 KB Output is correct
7 Correct 6 ms 7552 KB Output is correct
8 Correct 7 ms 7552 KB Output is correct
9 Correct 14 ms 8064 KB Output is correct
10 Correct 34 ms 9984 KB Output is correct
11 Correct 189 ms 18168 KB Output is correct
12 Correct 103 ms 18168 KB Output is correct
13 Correct 156 ms 18040 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 12280 KB Output is correct
2 Correct 373 ms 26616 KB Output is correct
3 Correct 136 ms 22516 KB Output is correct
4 Correct 135 ms 13816 KB Output is correct
5 Correct 146 ms 13632 KB Output is correct
6 Correct 136 ms 13560 KB Output is correct
7 Correct 141 ms 12792 KB Output is correct
8 Correct 59 ms 12280 KB Output is correct
9 Correct 287 ms 27128 KB Output is correct
10 Correct 382 ms 26708 KB Output is correct
11 Correct 255 ms 26648 KB Output is correct
12 Correct 429 ms 24824 KB Output is correct
13 Correct 181 ms 28280 KB Output is correct
14 Correct 134 ms 22388 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 17272 KB Output is correct
2 Correct 597 ms 25208 KB Output is correct
3 Correct 355 ms 26232 KB Output is correct
4 Correct 280 ms 23160 KB Output is correct
5 Correct 330 ms 22756 KB Output is correct
6 Correct 307 ms 22780 KB Output is correct
7 Correct 325 ms 21556 KB Output is correct
8 Correct 402 ms 26360 KB Output is correct
9 Correct 566 ms 27384 KB Output is correct
10 Correct 716 ms 26984 KB Output is correct
11 Correct 720 ms 27128 KB Output is correct
12 Correct 599 ms 25336 KB Output is correct
13 Correct 713 ms 31524 KB Output is correct
14 Correct 246 ms 23156 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 27400 KB Output is correct
2 Correct 500 ms 25336 KB Output is correct
3 Correct 178 ms 30840 KB Output is correct
4 Correct 501 ms 27384 KB Output is correct
5 Correct 472 ms 27080 KB Output is correct
6 Correct 279 ms 26744 KB Output is correct
7 Correct 514 ms 25464 KB Output is correct
8 Correct 194 ms 31004 KB Output is correct
9 Correct 137 ms 22644 KB Output is correct