oj.uz

Submission #282982

# Submission time Handle Problem Language Result Execution time Memory
282982 2020-08-25T08:09:21 Z egekabas Ball Machine (BOI13_ballmachine) C++14
100 / 100
 301 ms 27128 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n, q;
int bit[100009];
int get(int idx){
    int ret = 0;
    for(++idx; idx > 0; idx -= idx&(-idx))
        ret += bit[idx];
    return ret;
}
void upd(int idx, int val){
    for(++idx; idx <= n; idx += idx&(-idx))
        bit[idx] += val;
}
void updrange(int l, int r, int val){
    upd(l, val);
    upd(r+1, -val);
}
int val[100009];
vector<int> g[100009];
int root;
int dad[100009][20];
void dfs1(int v){
    for(int i = 1; i < 20; ++i)
        dad[v][i] = dad[dad[v][i-1]][i-1];
    for(auto u : g[v]){
        dad[u][0] = v;
        dfs1(u);
        val[v] = min(val[v], val[u]);
    }
}
int sf(int x, int y){
    return val[x] < val[y];
}
int tin[100009];
int tout[100009];
int ord[100009];
int curtime = 0;
int curord = 0;
void dfs2(int v){
    sort(all(g[v]), sf);
    tin[v] = curtime++;
    for(auto u : g[v]){
        dfs2(u);
    }
    tout[v] = curtime-1;
    ord[v] = curord++;
}
int goup(int v, int x){
    for(int i = 19; i >= 0; --i)
        if(x&(1<<i))
            v = dad[v][i];
    return v;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        val[i] = i;
        int prt;
        cin >> prt;
        if(prt == 0)
            root = i;
        else
            g[prt].pb(i);
    }
    dfs1(root);
    dfs2(root);
    set<pii> s;
    for(int i = 1; i <= n; ++i)
        s.insert({ord[i], i});
    while(q--){
        int t, k;
        cin >> t >> k;
        if(t == 1){
            int last;
            while(k--){
                last = s.begin()->ss;
                s.erase(s.begin());
                updrange(tin[last], tout[last], 1);
            }
            cout << last << '\n';
        }
        else{
            int rolldown = get(tin[k])-1;
            cout << rolldown << '\n';
            int v = goup(k, rolldown);
            s.insert({ord[v], v});
            updrange(tin[v], tout[v], -1);
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:99:29: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |             cout << last << '\n';
      |                             ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 168 ms 14072 KB Output is correct
3 Correct 97 ms 14076 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2944 KB Output is correct
8 Correct 3 ms 2944 KB Output is correct
9 Correct 10 ms 3456 KB Output is correct
10 Correct 28 ms 5632 KB Output is correct
11 Correct 163 ms 13944 KB Output is correct
12 Correct 98 ms 14072 KB Output is correct
13 Correct 135 ms 13872 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7804 KB Output is correct
2 Correct 229 ms 22956 KB Output is correct
3 Correct 117 ms 19012 KB Output is correct
4 Correct 82 ms 9464 KB Output is correct
5 Correct 82 ms 9336 KB Output is correct
6 Correct 73 ms 9208 KB Output is correct
7 Correct 75 ms 8440 KB Output is correct
8 Correct 41 ms 7800 KB Output is correct
9 Correct 205 ms 23416 KB Output is correct
10 Correct 237 ms 22912 KB Output is correct
11 Correct 194 ms 22776 KB Output is correct
12 Correct 239 ms 20984 KB Output is correct
13 Correct 155 ms 24056 KB Output is correct
14 Correct 125 ms 18292 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 12920 KB Output is correct
2 Correct 282 ms 21060 KB Output is correct
3 Correct 177 ms 22108 KB Output is correct
4 Correct 181 ms 18936 KB Output is correct
5 Correct 191 ms 18552 KB Output is correct
6 Correct 182 ms 18644 KB Output is correct
7 Correct 175 ms 17400 KB Output is correct
8 Correct 186 ms 22008 KB Output is correct
9 Correct 271 ms 23032 KB Output is correct
10 Correct 273 ms 22648 KB Output is correct
11 Correct 273 ms 22780 KB Output is correct
12 Correct 301 ms 21216 KB Output is correct
13 Correct 270 ms 27128 KB Output is correct
14 Correct 207 ms 18748 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 23032 KB Output is correct
2 Correct 281 ms 20984 KB Output is correct
3 Correct 188 ms 26616 KB Output is correct
4 Correct 267 ms 23164 KB Output is correct
5 Correct 267 ms 22520 KB Output is correct
6 Correct 214 ms 22184 KB Output is correct
7 Correct 273 ms 20984 KB Output is correct
8 Correct 177 ms 26616 KB Output is correct
9 Correct 122 ms 18420 KB Output is correct