oj.uz

Submission #42698

# Submission time Handle Problem Language Result Execution time Memory
42698 2018-03-02T20:38:48 Z Hassoony Ball Machine (BOI13_ballmachine) C++14
0 / 100
 217 ms 26124 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,int p){
    mn[x]=x;
    for(auto pp:v[x]){
        if(pp==p)continue;
        dfs(pp,x);
        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,int p){
    for(auto pp:v[x]){
        if(pp==p)continue;
        dfs(pp,x);
    }
    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);
        v[i].push_back(x);
    }
    dfs(root,-1);
    build();
    pro(root,-1);
    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:34: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:37:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
ballmachine.cpp:48: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 5 ms 5116 KB Output isn't correct
2 Incorrect 108 ms 13408 KB Output isn't correct
3 Incorrect 81 ms 13668 KB Output isn't correct
4 Incorrect 5 ms 13668 KB Output isn't correct
5 Incorrect 5 ms 13668 KB Output isn't correct
6 Incorrect 5 ms 13668 KB Output isn't correct
7 Incorrect 6 ms 13668 KB Output isn't correct
8 Incorrect 6 ms 13668 KB Output isn't correct
9 Incorrect 11 ms 13668 KB Output isn't correct
10 Incorrect 27 ms 13668 KB Output isn't correct
11 Incorrect 106 ms 13668 KB Output isn't correct
12 Incorrect 93 ms 13792 KB Output isn't correct
13 Incorrect 105 ms 13792 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 13792 KB Output isn't correct
2 Incorrect 179 ms 21988 KB Output isn't correct
3 Incorrect 99 ms 21988 KB Output isn't correct
4 Incorrect 70 ms 21988 KB Output isn't correct
5 Incorrect 77 ms 21988 KB Output isn't correct
6 Incorrect 79 ms 21988 KB Output isn't correct
7 Incorrect 70 ms 21988 KB Output isn't correct
8 Incorrect 47 ms 21988 KB Output isn't correct
9 Incorrect 143 ms 21988 KB Output isn't correct
10 Incorrect 173 ms 21988 KB Output isn't correct
11 Incorrect 182 ms 22160 KB Output isn't correct
12 Incorrect 151 ms 22160 KB Output isn't correct
13 Incorrect 116 ms 23240 KB Output isn't correct
14 Incorrect 107 ms 23240 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 23240 KB Output isn't correct
2 Incorrect 177 ms 23240 KB Output isn't correct
3 Incorrect 128 ms 23240 KB Output isn't correct
4 Incorrect 110 ms 23240 KB Output isn't correct
5 Incorrect 128 ms 23240 KB Output isn't correct
6 Incorrect 125 ms 23240 KB Output isn't correct
7 Incorrect 106 ms 23240 KB Output isn't correct
8 Incorrect 130 ms 23240 KB Output isn't correct
9 Incorrect 165 ms 23240 KB Output isn't correct
10 Incorrect 189 ms 23240 KB Output isn't correct
11 Incorrect 171 ms 23240 KB Output isn't correct
12 Incorrect 173 ms 23240 KB Output isn't correct
13 Incorrect 201 ms 26124 KB Output isn't correct
14 Incorrect 143 ms 26124 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 26124 KB Output isn't correct
2 Incorrect 217 ms 26124 KB Output isn't correct
3 Incorrect 132 ms 26124 KB Output isn't correct
4 Incorrect 188 ms 26124 KB Output isn't correct
5 Incorrect 180 ms 26124 KB Output isn't correct
6 Incorrect 163 ms 26124 KB Output isn't correct
7 Incorrect 164 ms 26124 KB Output isn't correct
8 Incorrect 138 ms 26124 KB Output isn't correct
9 Incorrect 114 ms 26124 KB Output isn't correct