oj.uz

Submission #492756

# Submission time Handle Problem Language Result Execution time Memory
492756 2021-12-08T19:58:57 Z nickmet2004 Ball Machine (BOI13_ballmachine) C++11
100 / 100
 302 ms 27956 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int n , q;
vector<int> adj[N];
int S[N] , P[N][20] , R , A[N] , B[N] ,C[N], b;
void dfs(int u, int p){
    S[u]=u;
    P[u][0]= p;
    for(int i = 1; i<= 18; ++i) P[u][i]= P[P[u][i - 1]][i - 1];
    for(int v : adj[u]){
        dfs(v,u);
        S[u] = min(S[u], S[v]);
    }
}
void DFS(int u){
    for(int v : adj[u]) DFS(v);
    B[++b] = u;
}
bool cmp(int a, int b){
    return S[a] < S[b];
}
int k = 0;
int Q(int u){
    for(int i = 17; ~i; --i){
        int y = P[u][i];
        if(C[y]) u = y ,k += (1 <<i);
    }
    return u;
}

int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    int a;
    for(int i= 1; i <=n; ++i){
        cin >> a;
        if(a==0)R = i;
        else adj[a].emplace_back(i);
    }
    for(int i = 1;i <= n; ++i) S[i] = 2e9;
    dfs(R,0);
    for(int i= 1; i<= n; ++i)sort(adj[i].begin() ,adj[i].end() , cmp);
    DFS(R);
    //for(int i = 1; i<= n; ++i)cout << B[i] << " ";cout << endl;
    for(int i = 1; i <= n; ++i) A[B[i]] = i;
    set<int> s;
    for(int i = 1; i<= n; ++i)s.insert(i);
    while(q--){
        int d;
        cin >> d;
        if(d==1){
            int x;
            cin >> x;
            int g = 0;
            while(x--){
                g = *s.begin();
                s.erase(s.begin());
                C[B[g]] =1;
            }
            cout << B[g]<<endl;
        }else{
            int u; cin>>u;
            int h = Q(u);
            cout << k << endl;k=0;
            s.insert(A[h]);
            C[h]=0;
        }
    }

return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 219 ms 14188 KB Output is correct
3 Correct 176 ms 13972 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 4 ms 2764 KB Output is correct
8 Correct 4 ms 2764 KB Output is correct
9 Correct 15 ms 3420 KB Output is correct
10 Correct 42 ms 5492 KB Output is correct
11 Correct 215 ms 14256 KB Output is correct
12 Correct 181 ms 14240 KB Output is correct
13 Correct 209 ms 14172 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 7628 KB Output is correct
2 Correct 268 ms 23344 KB Output is correct
3 Correct 193 ms 18748 KB Output is correct
4 Correct 146 ms 9436 KB Output is correct
5 Correct 154 ms 9292 KB Output is correct
6 Correct 148 ms 9448 KB Output is correct
7 Correct 149 ms 8324 KB Output is correct
8 Correct 121 ms 7604 KB Output is correct
9 Correct 257 ms 23724 KB Output is correct
10 Correct 267 ms 23344 KB Output is correct
11 Correct 250 ms 23236 KB Output is correct
12 Correct 256 ms 21316 KB Output is correct
13 Correct 223 ms 24448 KB Output is correct
14 Correct 194 ms 18740 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 13300 KB Output is correct
2 Correct 280 ms 21900 KB Output is correct
3 Correct 212 ms 22600 KB Output is correct
4 Correct 172 ms 19396 KB Output is correct
5 Correct 183 ms 19064 KB Output is correct
6 Correct 168 ms 19056 KB Output is correct
7 Correct 184 ms 17932 KB Output is correct
8 Correct 190 ms 22696 KB Output is correct
9 Correct 291 ms 23876 KB Output is correct
10 Correct 273 ms 23608 KB Output is correct
11 Correct 297 ms 23504 KB Output is correct
12 Correct 286 ms 21940 KB Output is correct
13 Correct 296 ms 27956 KB Output is correct
14 Correct 232 ms 19660 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 24080 KB Output is correct
2 Correct 289 ms 21884 KB Output is correct
3 Correct 232 ms 27292 KB Output is correct
4 Correct 302 ms 24152 KB Output is correct
5 Correct 290 ms 23500 KB Output is correct
6 Correct 255 ms 23360 KB Output is correct
7 Correct 297 ms 21952 KB Output is correct
8 Correct 233 ms 27204 KB Output is correct
9 Correct 207 ms 18880 KB Output is correct