oj.uz

Submission #239113

# Submission time Handle Problem Language Result Execution time Memory
239113 2020-06-14T12:38:21 Z Autoratch Ball Machine (BOI13_ballmachine) C++14
100 / 100
 177 ms 26728 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 1;
const int K = 19;

int n,q,root,t;
vector<int> adj[N];
int dp[K][N],lv[N],mn[N],prio[N];
priority_queue<pair<int,int> > ava;
vector<pair<int,int> > tmp;
bool filled[N];

void dfs(int u,int p)
{
    lv[u] = lv[p]+1,dp[0][u] = p;
    mn[u] = u;
    for(int v : adj[u]) dfs(v,u),mn[u] = min(mn[u],mn[v]);
    tmp.clear();
    for(int v : adj[u]) tmp.push_back({mn[v],v});
    sort(tmp.begin(),tmp.end());
    int id = 0;
    for(int &v : adj[u]) v = tmp[id++].second;
}

void findpr(int u,int p)
{
    for(int v : adj[u]) findpr(v,u);
    prio[u] = ++t;
}

int jump(int x)
{
    for(int i = K-1;i >= 0;i--) if(filled[dp[i][x]])
    {
        x = dp[i][x];
        if(!filled[dp[0][x]]) return x;
    }
    return x;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> q;
    for(int i = 1;i <= n;i++) 
    {
        int x;
        cin >> x;
        if(!x) root = i;
        else adj[x].push_back(i);
    }
    dfs(root,0);
    findpr(root,0);
    for(int i = 1;i < K;i++) for(int j = 1;j <= n;j++) dp[i][j] = dp[i-1][dp[i-1][j]];
    for(int i = 1;i <= n;i++) ava.push({-prio[i],i});
    while(q--)
    {
        int t,x;
        cin >> t >> x;
        if(t==1)
        {
            int ans;
            while(x--) ans = ava.top().second,filled[ava.top().second] = true,ava.pop();            
            cout << ans << '\n';
        }
        else
        {
            int res = jump(x);
            filled[res] = false,ava.push({-prio[res],res});
            cout << lv[x]-lv[res] << '\n';
        }
    }
}

Compilation message

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 89 ms 11504 KB Output is correct
3 Correct 64 ms 11504 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2944 KB Output is correct
7 Correct 7 ms 2944 KB Output is correct
8 Correct 6 ms 2944 KB Output is correct
9 Correct 10 ms 3328 KB Output is correct
10 Correct 21 ms 4992 KB Output is correct
11 Correct 88 ms 11500 KB Output is correct
12 Correct 58 ms 11504 KB Output is correct
13 Correct 79 ms 11500 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7796 KB Output is correct
2 Correct 153 ms 20460 KB Output is correct
3 Correct 76 ms 15212 KB Output is correct
4 Correct 53 ms 8824 KB Output is correct
5 Correct 56 ms 8692 KB Output is correct
6 Correct 55 ms 8692 KB Output is correct
7 Correct 52 ms 7672 KB Output is correct
8 Correct 36 ms 7796 KB Output is correct
9 Correct 125 ms 20976 KB Output is correct
10 Correct 136 ms 20460 KB Output is correct
11 Correct 110 ms 20552 KB Output is correct
12 Correct 144 ms 17960 KB Output is correct
13 Correct 95 ms 23788 KB Output is correct
14 Correct 74 ms 15212 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 12020 KB Output is correct
2 Correct 156 ms 18476 KB Output is correct
3 Correct 112 ms 21872 KB Output is correct
4 Correct 92 ms 17384 KB Output is correct
5 Correct 91 ms 17008 KB Output is correct
6 Correct 100 ms 17136 KB Output is correct
7 Correct 99 ms 15108 KB Output is correct
8 Correct 109 ms 21736 KB Output is correct
9 Correct 144 ms 21080 KB Output is correct
10 Correct 156 ms 20716 KB Output is correct
11 Correct 143 ms 20716 KB Output is correct
12 Correct 148 ms 18288 KB Output is correct
13 Correct 177 ms 26728 KB Output is correct
14 Correct 110 ms 15724 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 21196 KB Output is correct
2 Correct 159 ms 18316 KB Output is correct
3 Correct 102 ms 26344 KB Output is correct
4 Correct 168 ms 21204 KB Output is correct
5 Correct 150 ms 20720 KB Output is correct
6 Correct 117 ms 20720 KB Output is correct
7 Correct 145 ms 18412 KB Output is correct
8 Correct 101 ms 26348 KB Output is correct
9 Correct 67 ms 15212 KB Output is correct