oj.uz

Submission #854873

# Submission time Handle Problem Language Result Execution time Memory
854873 2023-09-29T08:05:14 Z Essa2006 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 250 ms 32732 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 104 ms 15112 KB Output is correct
3 Correct 83 ms 15472 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 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 1372 KB Output is correct
10 Correct 19 ms 4004 KB Output is correct
11 Correct 140 ms 15052 KB Output is correct
12 Correct 64 ms 15372 KB Output is correct
13 Correct 108 ms 15336 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6608 KB Output is correct
2 Correct 197 ms 27076 KB Output is correct
3 Correct 91 ms 22472 KB Output is correct
4 Correct 58 ms 8656 KB Output is correct
5 Correct 63 ms 8408 KB Output is correct
6 Correct 58 ms 8464 KB Output is correct
7 Correct 57 ms 7376 KB Output is correct
8 Correct 30 ms 6356 KB Output is correct
9 Correct 169 ms 27592 KB Output is correct
10 Correct 203 ms 27008 KB Output is correct
11 Correct 219 ms 27380 KB Output is correct
12 Correct 175 ms 24712 KB Output is correct
13 Correct 136 ms 28776 KB Output is correct
14 Correct 91 ms 22468 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 14064 KB Output is correct
2 Correct 195 ms 25412 KB Output is correct
3 Correct 173 ms 26108 KB Output is correct
4 Correct 127 ms 22316 KB Output is correct
5 Correct 143 ms 21852 KB Output is correct
6 Correct 147 ms 21788 KB Output is correct
7 Correct 141 ms 20168 KB Output is correct
8 Correct 151 ms 26052 KB Output is correct
9 Correct 179 ms 27644 KB Output is correct
10 Correct 216 ms 27404 KB Output is correct
11 Correct 226 ms 27332 KB Output is correct
12 Correct 207 ms 25288 KB Output is correct
13 Correct 241 ms 32732 KB Output is correct
14 Correct 145 ms 22644 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 27844 KB Output is correct
2 Correct 250 ms 25392 KB Output is correct
3 Correct 160 ms 32428 KB Output is correct
4 Correct 222 ms 27724 KB Output is correct
5 Correct 205 ms 27260 KB Output is correct
6 Correct 178 ms 27208 KB Output is correct
7 Correct 203 ms 25284 KB Output is correct
8 Correct 151 ms 32396 KB Output is correct
9 Correct 100 ms 22728 KB Output is correct