oj.uz

답안 #854872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854872 2023-09-29T08:02:07 Z Essa2006 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 290 ms 32716 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int lg=20;
int n, q, cur;
vector<int>P, Has_ball, Mn;
vector<vector<int> >A, Up;
priority_queue<array<int, 2> >pq;
map<int, int>mp;

void pre(){
    P.clear(), Has_ball.clear(), Mn.clear(), A.clear(), Up.clear(), mp.clear();
    P.resize(n+1), Has_ball.resize(n+1), Mn.resize(n+1), A.resize(n+1), Up.resize(n+1, vector<int>(lg+1));
}

bool cmp(int a, int b){
    return Mn[a]<Mn[b];
}

void dfs(int u){
    Mn[u]=u;
    Up[u][0]=P[u];
    for(int j=1;j<=lg;j++){
        Up[u][j]=Up[Up[u][j-1]][j-1];
    }
    for(auto v:A[u]){
        dfs(v);
        Mn[u]=min(Mn[u], Mn[v]);
    }
    sort(all(A[u]), cmp);
    
}


void ord(int u){
    for(auto v:A[u]){
        ord(v);
    }
    mp[u]=cur;
    array<int, 2>a={-cur, u};
    pq.push(a);
    cur++;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    pre();
    int root;
    for(int i=1;i<=n;i++){
        int p, u=i;
        cin>>p;
        if(!p)
            root=u;
        else{
            A[p].push_back(u);
            P[u]=p;
        }
    }
    dfs(root), ord(root);
    while(q--){
        int type, k;
        cin>>type>>k;
        int ans=0;
        if(type==1){
            // add k balls and print the last postion
            while(k--){
                int u=pq.top()[1];
                pq.pop();
                Has_ball[u]=1;
                ans=u;
            }
        }
        else if(type==2){
            // remove ball in node k and print the number of balls in nodes above node k
            for(int j=lg;j>=0;j--){
                int v=Up[k][j];
                if(Has_ball[v])
                    ans+=(1<<j), k=v;
            }
            Has_ball[k]=0;
            array<int, 2>a={-mp[k], k};
            pq.push(a);
        }
        cout<<ans<<endl;
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:65:19: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |     dfs(root), ord(root);
      |                ~~~^~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 102 ms 15180 KB Output is correct
3 Correct 67 ms 15308 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 5 ms 1384 KB Output is correct
10 Correct 20 ms 3932 KB Output is correct
11 Correct 104 ms 15216 KB Output is correct
12 Correct 66 ms 15300 KB Output is correct
13 Correct 136 ms 15196 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 6360 KB Output is correct
2 Correct 197 ms 27232 KB Output is correct
3 Correct 97 ms 22780 KB Output is correct
4 Correct 65 ms 8652 KB Output is correct
5 Correct 60 ms 8404 KB Output is correct
6 Correct 58 ms 8504 KB Output is correct
7 Correct 60 ms 7376 KB Output is correct
8 Correct 30 ms 6360 KB Output is correct
9 Correct 195 ms 27588 KB Output is correct
10 Correct 210 ms 27132 KB Output is correct
11 Correct 202 ms 27076 KB Output is correct
12 Correct 185 ms 24516 KB Output is correct
13 Correct 138 ms 28764 KB Output is correct
14 Correct 92 ms 22468 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 14108 KB Output is correct
2 Correct 199 ms 25232 KB Output is correct
3 Correct 150 ms 26056 KB Output is correct
4 Correct 128 ms 22260 KB Output is correct
5 Correct 128 ms 21816 KB Output is correct
6 Correct 126 ms 21924 KB Output is correct
7 Correct 147 ms 20208 KB Output is correct
8 Correct 178 ms 26276 KB Output is correct
9 Correct 182 ms 27632 KB Output is correct
10 Correct 209 ms 27332 KB Output is correct
11 Correct 205 ms 27436 KB Output is correct
12 Correct 207 ms 25284 KB Output is correct
13 Correct 290 ms 32716 KB Output is correct
14 Correct 127 ms 22744 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 27748 KB Output is correct
2 Correct 227 ms 25292 KB Output is correct
3 Correct 156 ms 32456 KB Output is correct
4 Correct 195 ms 27848 KB Output is correct
5 Correct 212 ms 27492 KB Output is correct
6 Correct 179 ms 27332 KB Output is correct
7 Correct 193 ms 25304 KB Output is correct
8 Correct 163 ms 32588 KB Output is correct
9 Correct 87 ms 22724 KB Output is correct