oj.uz

답안 #42696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42696 2018-03-02T20:33:10 Z Hassoony Ball Machine (BOI13_ballmachine) C++14
0 / 100
 234 ms 26084 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){
    for(auto pp:v[x]){
        if(pp==p)continue;
        dp[0][pp]=x;
        dfs(pp,x);
        mn[x]=min(mn[x],mn[pp]);
    }
    mn[x]=min(mn[x],x);
    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);
        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:35: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:38: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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 5112 KB Output isn't correct
2 Incorrect 112 ms 13560 KB Output isn't correct
3 Incorrect 84 ms 13592 KB Output isn't correct
4 Incorrect 5 ms 13592 KB Output isn't correct
5 Incorrect 5 ms 13592 KB Output isn't correct
6 Incorrect 5 ms 13592 KB Output isn't correct
7 Incorrect 5 ms 13592 KB Output isn't correct
8 Incorrect 6 ms 13592 KB Output isn't correct
9 Incorrect 11 ms 13592 KB Output isn't correct
10 Incorrect 26 ms 13592 KB Output isn't correct
11 Incorrect 104 ms 13684 KB Output isn't correct
12 Incorrect 80 ms 13828 KB Output isn't correct
13 Incorrect 107 ms 13828 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 13828 KB Output isn't correct
2 Incorrect 180 ms 22000 KB Output isn't correct
3 Incorrect 105 ms 22000 KB Output isn't correct
4 Incorrect 69 ms 22000 KB Output isn't correct
5 Incorrect 76 ms 22000 KB Output isn't correct
6 Incorrect 77 ms 22000 KB Output isn't correct
7 Incorrect 70 ms 22000 KB Output isn't correct
8 Incorrect 46 ms 22000 KB Output isn't correct
9 Incorrect 162 ms 22000 KB Output isn't correct
10 Incorrect 168 ms 22000 KB Output isn't correct
11 Incorrect 169 ms 22176 KB Output isn't correct
12 Incorrect 152 ms 22176 KB Output isn't correct
13 Incorrect 120 ms 23456 KB Output isn't correct
14 Incorrect 133 ms 23456 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 74 ms 23456 KB Output isn't correct
2 Incorrect 175 ms 23456 KB Output isn't correct
3 Incorrect 125 ms 23456 KB Output isn't correct
4 Incorrect 111 ms 23456 KB Output isn't correct
5 Incorrect 110 ms 23456 KB Output isn't correct
6 Incorrect 115 ms 23456 KB Output isn't correct
7 Incorrect 114 ms 23456 KB Output isn't correct
8 Incorrect 122 ms 23456 KB Output isn't correct
9 Incorrect 160 ms 23456 KB Output isn't correct
10 Incorrect 187 ms 23456 KB Output isn't correct
11 Incorrect 171 ms 23456 KB Output isn't correct
12 Incorrect 173 ms 23456 KB Output isn't correct
13 Incorrect 234 ms 26084 KB Output isn't correct
14 Incorrect 139 ms 26084 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 160 ms 26084 KB Output isn't correct
2 Incorrect 168 ms 26084 KB Output isn't correct
3 Incorrect 132 ms 26084 KB Output isn't correct
4 Incorrect 173 ms 26084 KB Output isn't correct
5 Incorrect 171 ms 26084 KB Output isn't correct
6 Incorrect 157 ms 26084 KB Output isn't correct
7 Incorrect 160 ms 26084 KB Output isn't correct
8 Incorrect 115 ms 26084 KB Output isn't correct
9 Incorrect 96 ms 26084 KB Output isn't correct