oj.uz

Submission #834983

# Submission time Handle Problem Language Result Execution time Memory
834983 2023-08-23T04:36:18 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
0 / 100
 50 ms 26636 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
vector<vector<ll>>graf;
vector<ll>minkir, minkan, atas;
vector<bool>penuh;
int total, akh;
void dfs(ll x, ll akhir) {
    for(auto it:graf[x]) {
        if(it == akhir) continue;
        dfs(it,x);
    }
    if(graf[x].size()) {
        minkir[x] = LLONG_MAX;
        minkan[x] = LLONG_MAX;
        return;
    }
    minkir[x] = min(min(minkir[graf[x][0]], minkan[graf[x][0]]), graf[x][0]);
    minkan[x] = min(min(minkan[graf[x][0]], minkir[graf[x][0]]), graf[x][0]);
}
void tambah(int x) {
    if(graf[x].size() == 0 || (penuh[graf[x][0]] && penuh[graf[x][1]])) {
        penuh[x] = true;
        akh = x;
        return;
    }
    if(penuh[graf[x][1]]) {
        tambah(graf[x][0]);
    } else 
    if(penuh[graf[x][0]]) {
        tambah(graf[x][1]);
    } else 
    if(minkir[x] < minkan[x]) {
        tambah(graf[x][0]);
    } else {
        tambah(graf[x][1]);
    }
}
void hoek(int x, int akhir) {
    if(x==0) return;
    if(akhir != -1) {
        if(penuh[akhir]==false && penuh[x]==false) {
            penuh[akhir] = true;
            penuh[x] = false;
            total++;
        }
    }
    hoek(atas[x], x);
}
int main() {
    int N,Q,par;
    cin >> N >> Q;
    graf.resize(N+1);
    atas.resize(N+1);
    minkir.resize(N+1);
    minkan.resize(N+1);
    penuh.resize(N+1);
    int root;
    for(int i=1; i<=N; i++) {
        cin >> par;
        graf[par].pb(i);
        atas[i] = par;
        if(par == 0) root = i;
    }
    dfs(root,0);
    int jenis, k;
    while(Q--) {
        cin >> jenis >> k;
        if(jenis==1) {
            for(int i=0; i<k; i++) {
                tambah(root);
            }
            cout << akh << endl;
        } else {
            penuh[k] = false;
            total = 0;
            hoek(k,-1);
            cout << total << endl;
        }
    } 
    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:66:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |     dfs(root,0);
      |     ~~~^~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Runtime error 21 ms 9344 KB Execution killed with signal 11
3 Runtime error 21 ms 9300 KB Execution killed with signal 11
4 Runtime error 1 ms 308 KB Execution killed with signal 11
5 Runtime error 1 ms 428 KB Execution killed with signal 11
6 Runtime error 2 ms 468 KB Execution killed with signal 11
7 Runtime error 1 ms 468 KB Execution killed with signal 11
8 Runtime error 1 ms 468 KB Execution killed with signal 11
9 Runtime error 2 ms 956 KB Execution killed with signal 11
10 Runtime error 6 ms 2772 KB Execution killed with signal 11
11 Runtime error 21 ms 9388 KB Execution killed with signal 11
12 Runtime error 20 ms 9328 KB Execution killed with signal 11
13 Runtime error 21 ms 9412 KB Execution killed with signal 11

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 5192 KB Execution killed with signal 11
2 Runtime error 32 ms 14888 KB Execution killed with signal 11
3 Runtime error 29 ms 13880 KB Execution killed with signal 11
4 Runtime error 10 ms 5092 KB Execution killed with signal 11
5 Runtime error 10 ms 4820 KB Execution killed with signal 11
6 Runtime error 10 ms 4820 KB Execution killed with signal 11
7 Runtime error 9 ms 4596 KB Execution killed with signal 11
8 Runtime error 8 ms 5276 KB Execution killed with signal 11
9 Runtime error 32 ms 15704 KB Execution killed with signal 11
10 Runtime error 32 ms 14888 KB Execution killed with signal 11
11 Runtime error 32 ms 14928 KB Execution killed with signal 11
12 Runtime error 33 ms 14584 KB Execution killed with signal 11
13 Runtime error 45 ms 23524 KB Execution killed with signal 11
14 Runtime error 30 ms 13808 KB Execution killed with signal 11

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 8200 KB Execution killed with signal 11
2 Runtime error 33 ms 14876 KB Execution killed with signal 11
3 Runtime error 50 ms 21348 KB Execution killed with signal 11
4 Runtime error 26 ms 12756 KB Execution killed with signal 11
5 Runtime error 25 ms 12012 KB Execution killed with signal 11
6 Runtime error 26 ms 11968 KB Execution killed with signal 11
7 Runtime error 28 ms 11988 KB Execution killed with signal 11
8 Runtime error 32 ms 21328 KB Execution killed with signal 11
9 Runtime error 32 ms 15788 KB Execution killed with signal 11
10 Runtime error 33 ms 14956 KB Execution killed with signal 11
11 Runtime error 33 ms 14928 KB Execution killed with signal 11
12 Runtime error 33 ms 14964 KB Execution killed with signal 11
13 Runtime error 42 ms 26636 KB Execution killed with signal 11
14 Runtime error 30 ms 13912 KB Execution killed with signal 11

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 15788 KB Execution killed with signal 11
2 Runtime error 32 ms 14864 KB Execution killed with signal 11
3 Runtime error 44 ms 26520 KB Execution killed with signal 11
4 Runtime error 31 ms 15716 KB Execution killed with signal 11
5 Runtime error 31 ms 14892 KB Execution killed with signal 11
6 Runtime error 35 ms 14908 KB Execution killed with signal 11
7 Runtime error 32 ms 14916 KB Execution killed with signal 11
8 Runtime error 41 ms 26592 KB Execution killed with signal 11
9 Runtime error 30 ms 13880 KB Execution killed with signal 11