oj.uz

Submission #42699

# Submission time Handle Problem Language Result Execution time Memory
42699 2018-03-02T20:44:16 Z Hassoony Ball Machine (BOI13_ballmachine) C++14
0 / 100
 195 ms 24608 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){
    mn[x]=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])dfs(pp);
    out[x]=++timer;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        mn[i]=MX;
        scanf("%d",&x);
        dp[0][i]=x;
        if(x==0){root=i;continue;}
        v[x].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:30: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:33:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
ballmachine.cpp:43: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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Incorrect 109 ms 12540 KB Output isn't correct
3 Incorrect 77 ms 12620 KB Output isn't correct
4 Incorrect 5 ms 12620 KB Output isn't correct
5 Incorrect 5 ms 12620 KB Output isn't correct
6 Incorrect 8 ms 12620 KB Output isn't correct
7 Incorrect 6 ms 12620 KB Output isn't correct
8 Incorrect 6 ms 12620 KB Output isn't correct
9 Incorrect 10 ms 12620 KB Output isn't correct
10 Incorrect 24 ms 12620 KB Output isn't correct
11 Incorrect 101 ms 12680 KB Output isn't correct
12 Incorrect 75 ms 12904 KB Output isn't correct
13 Incorrect 97 ms 12904 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 12904 KB Output isn't correct
2 Incorrect 170 ms 20036 KB Output isn't correct
3 Incorrect 88 ms 20036 KB Output isn't correct
4 Incorrect 66 ms 20036 KB Output isn't correct
5 Incorrect 76 ms 20036 KB Output isn't correct
6 Incorrect 79 ms 20036 KB Output isn't correct
7 Incorrect 71 ms 20036 KB Output isn't correct
8 Incorrect 47 ms 20036 KB Output isn't correct
9 Incorrect 142 ms 20252 KB Output isn't correct
10 Incorrect 157 ms 20252 KB Output isn't correct
11 Incorrect 155 ms 20256 KB Output isn't correct
12 Incorrect 156 ms 20256 KB Output isn't correct
13 Incorrect 114 ms 21796 KB Output isn't correct
14 Incorrect 96 ms 21796 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 21796 KB Output isn't correct
2 Incorrect 141 ms 21796 KB Output isn't correct
3 Incorrect 127 ms 21796 KB Output isn't correct
4 Incorrect 121 ms 21796 KB Output isn't correct
5 Incorrect 103 ms 21796 KB Output isn't correct
6 Incorrect 106 ms 21796 KB Output isn't correct
7 Incorrect 112 ms 21796 KB Output isn't correct
8 Incorrect 120 ms 21796 KB Output isn't correct
9 Incorrect 157 ms 21796 KB Output isn't correct
10 Incorrect 158 ms 21796 KB Output isn't correct
11 Incorrect 168 ms 21796 KB Output isn't correct
12 Incorrect 173 ms 21796 KB Output isn't correct
13 Incorrect 195 ms 24608 KB Output isn't correct
14 Incorrect 117 ms 24608 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 24608 KB Output isn't correct
2 Incorrect 157 ms 24608 KB Output isn't correct
3 Incorrect 115 ms 24608 KB Output isn't correct
4 Incorrect 160 ms 24608 KB Output isn't correct
5 Incorrect 151 ms 24608 KB Output isn't correct
6 Incorrect 139 ms 24608 KB Output isn't correct
7 Incorrect 149 ms 24608 KB Output isn't correct
8 Incorrect 128 ms 24608 KB Output isn't correct
9 Incorrect 91 ms 24608 KB Output isn't correct