Submission #71842

#	Time	Username	Problem	Language	Result	Execution time	Memory
71842		doowey	Ball Machine (BOI13_ballmachine)	C++14	47.88 / 100	278 ms	49408 KiB

ballmachine

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double db;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO std::ios::sync_with_stdio(false);cin.tie(NULL);
#define TEST freopen("in.txt","r",stdin);
#define ones(a) __builtin_popcount(a);
#define pq priority_queue

const int N = (int)1e5 + 9;
const int LOG = 18;
vector<int> T[N];
int min_leaf[N];
int up[N][LOG];

void dfs1(int node,int par){
  min_leaf[node] = 21344567;
  up[node][0] = par;
  for(int i = 1;i < LOG;i ++ ){
    if(up[node][i - 1] != -1)
      up[node][i] = up[up[node][i - 1]][i - 1];
  }
  for(auto x : T[node]){
    dfs1(x, node);
    min_leaf[node] = min(min_leaf[node], min_leaf[x]);
  }
  if(T[node].empty())
    min_leaf[node] = node;
}

int tt;
int porder[N];
int pos[N];
bool is[N]; 

void dfs2(int node){
  vector<pii> nex;
  porder[tt] = node;
  pos[node] = tt++;
  for(auto x : T[node])
    nex.push_back(mp(min_leaf[x], x));
  sort(nex.begin(), nex.end());
  for(int i = (int)nex.size() - 1;i >= 0;i -- ){
    dfs2(nex[i].se);
  }
}

pq<int> emp;

int ins(int k){
  int fr;
  for(int i = 0;i < k;i ++ ){
    fr = emp.top();
    emp.pop();
    is[porder[fr]] = true;
  }
  return porder[fr];
}

int rem(int ix){
  int sum = 0;
  int go = ix;
  for(int i = LOG-1;i >= 0 ;i -- ){
    if(up[go][i] == -1)
      continue;
    if(is[up[go][i]]){
      sum += (1 << i);
      go = up[go][i];
    }
  }
  is[go] = false;
  emp.push(pos[go]);
  return sum;
}

int main(){
  fastIO;
  memset(up, -1, sizeof up);
  int n, q;
  cin >> n >> q;
  for(int i = 0;i <= n;i ++ )
    is[i] = false;
  int x;
  int root;
  for(int i = 1;i <= n;i ++ ){
    cin >> x;
    if(x == 0)
      root = i;
    else
      T[x].push_back(i);
  }
  dfs1(root, -1);
  dfs2(root);
  for(int i = 0;i < tt;i ++ )
    emp.push(i);
  int ty, bl;
  for(int i = 0;i < q;i ++ ){
    cin >> ty >> bl;
    if(ty == 1)
      cout << ins(bl) << "\n";
    else
      cout << rem(bl) << "\n";
  }
  return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int ins(int)':
ballmachine.cpp:60:7: warning: 'fr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int fr;
       ^~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:60:7: warning: 'fr' may be used uninitialized in this function [-Wmaybe-uninitialized]
ballmachine.cpp:102:7: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   dfs2(root);
   ~~~~^~~~~~

• Subtask 1: 1.9230769230769231 / 25
• Subtask 2: 12.857142857142858 / 30
• Subtask 3: 31.428571428571427 / 40
• Subtask 4: 1.6666666666666667 / 5