Submission #854871

#	Time	Username	Problem	Language	Result	Execution time	Memory
854871		Essa2006	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	240 ms	33896 KiB

ballmachine

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
//#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 (stderr)

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

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5