oj.uz

답안 #43593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43593 2018-03-18T04:22:45 Z PowerOfNinjaGo Ball Machine (BOI13_ballmachine) C++14
100 / 100
 270 ms 68572 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 141 ms 12112 KB Output is correct
3 Correct 78 ms 13008 KB Output is correct
4 Correct 3 ms 13008 KB Output is correct
5 Correct 5 ms 13008 KB Output is correct
6 Correct 4 ms 13008 KB Output is correct
7 Correct 4 ms 13008 KB Output is correct
8 Correct 4 ms 13008 KB Output is correct
9 Correct 13 ms 13008 KB Output is correct
10 Correct 33 ms 13008 KB Output is correct
11 Correct 118 ms 14788 KB Output is correct
12 Correct 72 ms 15628 KB Output is correct
13 Correct 99 ms 16924 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 16924 KB Output is correct
2 Correct 177 ms 26232 KB Output is correct
3 Correct 99 ms 26232 KB Output is correct
4 Correct 89 ms 26232 KB Output is correct
5 Correct 74 ms 26232 KB Output is correct
6 Correct 80 ms 26232 KB Output is correct
7 Correct 76 ms 26232 KB Output is correct
8 Correct 42 ms 26232 KB Output is correct
9 Correct 175 ms 32616 KB Output is correct
10 Correct 182 ms 33420 KB Output is correct
11 Correct 165 ms 34816 KB Output is correct
12 Correct 188 ms 34816 KB Output is correct
13 Correct 145 ms 39248 KB Output is correct
14 Correct 91 ms 39248 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 39248 KB Output is correct
2 Correct 218 ms 39248 KB Output is correct
3 Correct 170 ms 41860 KB Output is correct
4 Correct 148 ms 41860 KB Output is correct
5 Correct 149 ms 41860 KB Output is correct
6 Correct 132 ms 41860 KB Output is correct
7 Correct 136 ms 41860 KB Output is correct
8 Correct 159 ms 46380 KB Output is correct
9 Correct 247 ms 47724 KB Output is correct
10 Correct 221 ms 48816 KB Output is correct
11 Correct 202 ms 50024 KB Output is correct
12 Correct 192 ms 50024 KB Output is correct
13 Correct 270 ms 57376 KB Output is correct
14 Correct 163 ms 57376 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 57376 KB Output is correct
2 Correct 238 ms 57376 KB Output is correct
3 Correct 146 ms 61932 KB Output is correct
4 Correct 234 ms 61932 KB Output is correct
5 Correct 207 ms 61932 KB Output is correct
6 Correct 177 ms 62012 KB Output is correct
7 Correct 230 ms 62012 KB Output is correct
8 Correct 174 ms 68572 KB Output is correct
9 Correct 100 ms 68572 KB Output is correct