oj.uz

Submission #26253

# Submission time Handle Problem Language Result Execution time Memory
26253 2017-06-28T15:14:34 Z WhipppedCream Ball Machine (BOI13_ballmachine) C++14
100 / 100
 309 ms 24628 KB 
#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vii vector< pair<int, int> >
typedef long long ll;
using namespace std;
vi adj[100005];
vi post;
int dp[22][100005];
int ft[100005];
int n;
int markdown[100005];
int pos[100005];
int minn[100005];
bool cmp(int a, int b)
{
    return minn[a]< minn[b];
}
void dfs(int u)
{
    minn[u] = u;
    for(auto v: adj[u])
    {
        dfs(v);
        minn[u] = min(minn[u], minn[v]);
    }
    sort(adj[u].begin(), adj[u].end(), cmp);
}
void dfs2(int u)
{
    for(auto v: adj[u]) dfs2(v);
    pos[u] = post.size();
    post.pb(u);
}
void add(int id, int dx)
{
    for(; id<= n; id += id&(-id)) ft[id] += dx;
}
int sum(int idx)
{
    int res = 0;
    for(; idx; idx -= idx&(-idx)) res += ft[idx];
    return res;
}
int findVacant()
{
    int lo = 1, hi = n;
    while(lo< hi)
    {
        int mid = (lo+hi)/2;
        if(sum(mid) > 0) hi = mid;
        else lo = mid+1;
    }
    add(lo, -1);
    markdown[post[lo]] = 1;
    return lo;
}
int findTop(int x)
{
    int cur = 20;
    int levs = 0;
    for(; cur>= 0; cur--)
    {
        int poss = dp[cur][x];
        if(poss == 0) continue;
        if(markdown[poss] == 1)
        {
            levs += (1<<cur);
            x = poss;
        }
    }
    add(pos[x], 1);
    markdown[x] = 0;
    return levs;
}
int main()
{
    int q;
    scanf("%d %d", &n, &q);
    int root = 0;
    post.pb(-1);
    for(int i = 1; i<= n; i++)
    {
        int p; scanf("%d", &p);
        adj[p].pb(i);
        dp[0][i] = p;
        if(p == 0) root = i;
        add(i, 1);
    }
    for(int i = 1; i<= 20; i++)
    {
        for(int j = 1; j<= n; j++)
        {
            dp[i][j] = dp[i-1][dp[i-1][j]];
        }
    }
    dfs(root);
    dfs2(root);
    while(q--)
    {
        int c, x; scanf("%d %d", &c, &x);
        if(c == 1)
        {
            int res = 0;
            while(x--) res = findVacant();
            printf("%d\n", post[res]);
        }
        else
        {
            printf("%d\n", findTop(x));
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:83:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
                           ^
ballmachine.cpp:88:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int p; scanf("%d", &p);
                               ^
ballmachine.cpp:105:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int c, x; scanf("%d %d", &c, &x);
                                         ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14524 KB Output is correct
2 Correct 126 ms 16012 KB Output is correct
3 Correct 79 ms 16012 KB Output is correct
4 Correct 0 ms 14524 KB Output is correct
5 Correct 0 ms 14524 KB Output is correct
6 Correct 0 ms 14524 KB Output is correct
7 Correct 3 ms 14524 KB Output is correct
8 Correct 0 ms 14524 KB Output is correct
9 Correct 9 ms 14656 KB Output is correct
10 Correct 26 ms 14920 KB Output is correct
11 Correct 106 ms 16012 KB Output is correct
12 Correct 86 ms 16012 KB Output is correct
13 Correct 116 ms 16012 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16336 KB Output is correct
2 Correct 179 ms 20328 KB Output is correct
3 Correct 86 ms 16932 KB Output is correct
4 Correct 89 ms 16260 KB Output is correct
5 Correct 106 ms 16124 KB Output is correct
6 Correct 93 ms 16124 KB Output is correct
7 Correct 83 ms 15644 KB Output is correct
8 Correct 49 ms 16336 KB Output is correct
9 Correct 169 ms 20744 KB Output is correct
10 Correct 219 ms 20320 KB Output is correct
11 Correct 166 ms 20328 KB Output is correct
12 Correct 193 ms 18684 KB Output is correct
13 Correct 139 ms 23528 KB Output is correct
14 Correct 89 ms 16932 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 17616 KB Output is correct
2 Correct 249 ms 18764 KB Output is correct
3 Correct 173 ms 22748 KB Output is correct
4 Correct 159 ms 19648 KB Output is correct
5 Correct 146 ms 19316 KB Output is correct
6 Correct 176 ms 19324 KB Output is correct
7 Correct 169 ms 18068 KB Output is correct
8 Correct 199 ms 22756 KB Output is correct
9 Correct 259 ms 20748 KB Output is correct
10 Correct 266 ms 20336 KB Output is correct
11 Correct 263 ms 20336 KB Output is correct
12 Correct 246 ms 18768 KB Output is correct
13 Correct 309 ms 24624 KB Output is correct
14 Correct 189 ms 16936 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 20740 KB Output is correct
2 Correct 233 ms 18764 KB Output is correct
3 Correct 143 ms 24620 KB Output is correct
4 Correct 263 ms 20744 KB Output is correct
5 Correct 209 ms 20332 KB Output is correct
6 Correct 186 ms 20340 KB Output is correct
7 Correct 223 ms 18768 KB Output is correct
8 Correct 153 ms 24628 KB Output is correct
9 Correct 106 ms 16936 KB Output is correct