oj.uz

Submission #493483

# Submission time Handle Problem Language Result Execution time Memory
493483 2021-12-11T15:33:10 Z SangTin Ball Machine (BOI13_ballmachine) C++14
100 / 100
 175 ms 29252 KB 
#include <bits/stdc++.h>

using namespace std;

#define name "BALLMACHINE"
#define endl '\n'
#define ednl endl
#define long long long
#define memset(a, x) memset(a, (x), sizeof(a));
#define inoutf freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define IN(a, b, c) (a <= b && b <= c)

template<typename T, typename U> inline bool amin(T &x, U y) { if(y >= x) return 0; x = y; return 1;}
template<typename T, typename U> inline bool amax(T &x, U y) { if(x >= y) return 0; x = y; return 1;}
template<typename T> inline void read(T& x){
    bool Neg = false;
    char c;
    for (c = getchar(); c < '0' | c > '9'; c = getchar())
        if (c == '-') Neg = !Neg;
    x = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    if (Neg) x = -x;
}

const int N = 1e5 + 83;
vector <int> Graph[N];
int Min[N], Priority[N], cnt = 0, pa[N][30], h[N], rePriority[N];
bool Have[N];

bool comp(int a, int b){
    return Min[a] < Min[b];
}

int dfs(bool sta, int u, int pa){
    if (sta && pa != -1) h[u] = h[pa] + 1;
    Min[u] = u;
    for (int &v : Graph[u]){
        amin(Min[u], dfs(sta, v, u));
    }
    if (sta){
        Priority[++cnt] = u;
        rePriority[u] = cnt;
    }
    return Min[u];
}

struct segtree{
    int Size;
    vector <int> ord;

    void init(int n){
        Size = n;
        ord.assign(4 * n, 0);
    }

    void update(int &i, int &p, int x, int lx, int rx){
        if (lx == rx){
            ord[x] = p;
            return;
        }
        int mid = (lx + rx) >> 1;
        if (mid < i) update(i, p, x << 1 | 1, mid + 1, rx);
        else update(i, p, x << 1, lx, mid);
        ord[x] = ord[x << 1] + ord[x << 1 | 1];
    }
    void update(int i, int p){update(i, p, 1, 1, Size);}

    int get_prio(int k, int x, int lx, int rx){
        if (lx == rx) return Priority[lx];
        int mid = (lx + rx) >> 1;
        if (ord[x << 1] < k) return get_prio(k - ord[x << 1], x << 1 | 1, mid + 1, rx);
        return get_prio(k, x << 1, lx, mid);
    }
    int get_prio(int k){return get_prio(k, 1, 1, Size);}
}st;

int LCA(int u){
    int log = log2(h[u]);
    for (int i = log; i >= 0; --i){
        if (pa[u][i] != -1 && Have[pa[u][i]]) u = pa[u][i];
    }
    return u;
}

int Solve(){
    int n, q; cin >> n >> q;
    memset(pa, -1);
    for (int i = 1; i <= n; ++i){
        cin >> pa[i][0];
        Graph[pa[i][0]].push_back(i);
    }
    dfs(0, 0, -1);
    for (int i = 1; i <= n; ++i){
        sort(Graph[i].begin(), Graph[i].end(), comp);
    }
    h[0] = 0;
    dfs(1, 0, -1);

    memset(Have, 0);
    st.init(n);
    for (int i = 1; i <= n; ++i) st.update(i, 1);

    int log = log2(n);
    for (int j = 1; j <= log; ++j){
        for (int i = 1; i <= n; ++i){
            if (pa[i][j - 1] == -1) continue;
            pa[i][j] = pa[pa[i][j - 1]][j - 1];
        }
    }

    while (q--){
        int sta, x; cin >> sta >> x;
        switch (sta){
            case 1:{
                int last;
                while(x--){
                    last = st.get_prio(1);
                    Have[last] = 1;
                    st.update(rePriority[last], 0);
                }
                cout << last << endl;
                break;
            }
            case 2:{
                int farPa = LCA(x);
                cout << h[x] - h[farPa] << endl;
                st.update(rePriority[farPa], 1);
                Have[farPa] = 0;
                break;
            }
        }
    }

    return 0;
}

int main(){
    fastio;

    int t = 1;
//    cin >> t;
    while (t--){
        Solve();
    }

    return 0;
}

Compilation message

ballmachine.cpp: In function 'int Solve()':
ballmachine.cpp:6:14: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
    6 | #define endl '\n'
      |              ^~~~
ballmachine.cpp:117:21: note: 'last' was declared here
  117 |                 int last;
      |                     ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14540 KB Output is correct
2 Correct 100 ms 17848 KB Output is correct
3 Correct 64 ms 18092 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 8 ms 14540 KB Output is correct
6 Correct 9 ms 14540 KB Output is correct
7 Correct 7 ms 14540 KB Output is correct
8 Correct 7 ms 14540 KB Output is correct
9 Correct 11 ms 14800 KB Output is correct
10 Correct 23 ms 15464 KB Output is correct
11 Correct 109 ms 18004 KB Output is correct
12 Correct 65 ms 18140 KB Output is correct
13 Correct 95 ms 17976 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17448 KB Output is correct
2 Correct 138 ms 23800 KB Output is correct
3 Correct 76 ms 19388 KB Output is correct
4 Correct 59 ms 17604 KB Output is correct
5 Correct 64 ms 17472 KB Output is correct
6 Correct 65 ms 17516 KB Output is correct
7 Correct 61 ms 16696 KB Output is correct
8 Correct 39 ms 17496 KB Output is correct
9 Correct 156 ms 24260 KB Output is correct
10 Correct 149 ms 23768 KB Output is correct
11 Correct 118 ms 23876 KB Output is correct
12 Correct 136 ms 21668 KB Output is correct
13 Correct 93 ms 27392 KB Output is correct
14 Correct 81 ms 19228 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 19504 KB Output is correct
2 Correct 158 ms 22044 KB Output is correct
3 Correct 104 ms 26192 KB Output is correct
4 Correct 96 ms 22328 KB Output is correct
5 Correct 96 ms 21988 KB Output is correct
6 Correct 100 ms 22108 KB Output is correct
7 Correct 95 ms 20372 KB Output is correct
8 Correct 108 ms 26244 KB Output is correct
9 Correct 148 ms 24440 KB Output is correct
10 Correct 156 ms 23908 KB Output is correct
11 Correct 146 ms 24008 KB Output is correct
12 Correct 174 ms 21944 KB Output is correct
13 Correct 164 ms 29252 KB Output is correct
14 Correct 118 ms 19308 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 24524 KB Output is correct
2 Correct 152 ms 22032 KB Output is correct
3 Correct 105 ms 29124 KB Output is correct
4 Correct 157 ms 24580 KB Output is correct
5 Correct 146 ms 24056 KB Output is correct
6 Correct 123 ms 24052 KB Output is correct
7 Correct 175 ms 21936 KB Output is correct
8 Correct 103 ms 29108 KB Output is correct
9 Correct 77 ms 19280 KB Output is correct