oj.uz

Submission #42700

# Submission time Handle Problem Language Result Execution time Memory
42700 2018-03-02T20:47:12 Z Hassoony Ball Machine (BOI13_ballmachine) C++14
100 / 100
 214 ms 25028 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=2e5+9;
const ll mod=1e8+6;
int n,q,dp[20][MX],ball[MX],mn[MX],timer,out[MX],x,t,root;
bool cmp(int A,int B){
    return mn[A]<mn[B];
}
vector<int>v[MX];
priority_queue<pair<int,int> >pq;
void dfs(int x){
    for(auto pp:v[x]){
        dfs(pp);
        mn[x]=min(mn[x],mn[pp]);
    }
    sort(v[x].begin(),v[x].end(),cmp);
}
void build(){
    for(int i=1;i<=18;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=dp[i-1][dp[i-1][j]];
}
void pro(int x){
    for(auto pp:v[x])pro(pp);
    out[x]=++timer;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        mn[i]=i;
        scanf("%d",&dp[0][i]);
        if(dp[0][i]==0){root=i;continue;}
        v[dp[0][i]].push_back(i);
    }
    dfs(root);
    build();
    pro(root);
    for(int i=1;i<=n;i++)pq.push({-out[i],i});
    while(q--){
        scanf("%d%d",&t,&x);
        if(t==1){
            int last=0;
            while(x--){
                ball[pq.top().second]=1;
                last=pq.top().second;
                pq.pop();
            }
            printf("%d\n",last);
        }
        else{
            int ans=0;
            for(int i=18;i>=0;i--){
                if(ball[dp[i][x]]){
                    x=dp[i][x];
                    ans+=(1<<i);
                }
            }
            ball[x]=0;
            pq.push({-out[x],x});
            printf("%d\n",ans);
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:29:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
                        ^
ballmachine.cpp:32:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&dp[0][i]);
                              ^
ballmachine.cpp:41:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&t,&x);
                            ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 123 ms 12636 KB Output is correct
3 Correct 67 ms 12636 KB Output is correct
4 Correct 5 ms 12636 KB Output is correct
5 Correct 5 ms 12636 KB Output is correct
6 Correct 6 ms 12636 KB Output is correct
7 Correct 6 ms 12636 KB Output is correct
8 Correct 6 ms 12636 KB Output is correct
9 Correct 10 ms 12636 KB Output is correct
10 Correct 24 ms 12636 KB Output is correct
11 Correct 102 ms 12936 KB Output is correct
12 Correct 73 ms 12936 KB Output is correct
13 Correct 107 ms 13024 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 13024 KB Output is correct
2 Correct 144 ms 20256 KB Output is correct
3 Correct 85 ms 20256 KB Output is correct
4 Correct 69 ms 20256 KB Output is correct
5 Correct 64 ms 20256 KB Output is correct
6 Correct 62 ms 20256 KB Output is correct
7 Correct 63 ms 20256 KB Output is correct
8 Correct 42 ms 20256 KB Output is correct
9 Correct 133 ms 20588 KB Output is correct
10 Correct 134 ms 20588 KB Output is correct
11 Correct 134 ms 20588 KB Output is correct
12 Correct 140 ms 20588 KB Output is correct
13 Correct 102 ms 22232 KB Output is correct
14 Correct 84 ms 22232 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 22232 KB Output is correct
2 Correct 172 ms 22232 KB Output is correct
3 Correct 144 ms 22232 KB Output is correct
4 Correct 101 ms 22232 KB Output is correct
5 Correct 103 ms 22232 KB Output is correct
6 Correct 98 ms 22232 KB Output is correct
7 Correct 97 ms 22232 KB Output is correct
8 Correct 132 ms 22232 KB Output is correct
9 Correct 163 ms 22232 KB Output is correct
10 Correct 150 ms 22232 KB Output is correct
11 Correct 160 ms 22232 KB Output is correct
12 Correct 160 ms 22232 KB Output is correct
13 Correct 214 ms 25028 KB Output is correct
14 Correct 123 ms 25028 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 25028 KB Output is correct
2 Correct 158 ms 25028 KB Output is correct
3 Correct 115 ms 25028 KB Output is correct
4 Correct 191 ms 25028 KB Output is correct
5 Correct 179 ms 25028 KB Output is correct
6 Correct 140 ms 25028 KB Output is correct
7 Correct 157 ms 25028 KB Output is correct
8 Correct 156 ms 25028 KB Output is correct
9 Correct 105 ms 25028 KB Output is correct