Submission #77369

#	Time	Username	Problem	Language	Result	Execution time	Memory
77369		xiaowuc1	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	936 ms	23492 KiB

ballmachine

#include <bits/stdc++.h>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);

ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/
using namespace std;

const double PI = 2 * acos(0);

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;

typedef pair<int, bool> pib;

const int MAX_N = 100000+1;
const int MAX_D = 16;
int lca[MAX_D][MAX_N];
int minValSubtree[MAX_N];
int depth[MAX_N];
vector<int> children[MAX_N];
int n;
int root;

int vertexOrder[MAX_N];
int _order;

bool ordercmp(int a, int b) {
  return vertexOrder[a] < vertexOrder[b];
}
bool subtreecmp(int a, int b) {
  return minValSubtree[a] < minValSubtree[b];
}

set<int, bool(*)(int, int)> avail(ordercmp);

void solve() {
  int t;
  scanf("%d", &t);
  int k;
  if(t == 1) {
    // insert k
    scanf("%d", &k);
    int last;
    while(k--) {
      last = *avail.begin();
      avail.erase(last);
    }
    printf("%d\n", last);
  }
  else {
    // remove from k
    scanf("%d", &k);
    int ret = 0;
    for(int d = MAX_D-1; d >= 0; d--) {
      while(depth[k] >= (1<<d) && !avail.count(lca[d][k])) {
        k = lca[d][k];
        ret += 1 << d;
      }
    }
    avail.insert(k);
    printf("%d\n", ret);
  }
}

void dfs(int curr) {
  minValSubtree[curr] = curr;
  for(int out: children[curr]) {
    dfs(out);
    minValSubtree[curr] = min(minValSubtree[curr], minValSubtree[out]);
  }
}

void genMin() {
  dfs(root);
}

void genOrder() {
  stack<pib> s;
  s.push(pib(root, false));
  while(!s.empty()) {
    pib curr = s.top();
    s.pop();
    if(curr.second) {
      vertexOrder[curr.first] = _order++;
    }
    else {
      s.push(pib(curr.first, true));
      for(int out: children[curr.first]) {
        s.push(pib(out, false));
      }
    }
  }
}

void genLCA() {
  queue<int> q;
  q.push(root);
  while(!q.empty()) {
    int curr = q.front();
    q.pop();
    sort(children[curr].begin(), children[curr].end(), subtreecmp);
    reverse(children[curr].begin(), children[curr].end());
    for(int out: children[curr]) {
      depth[out] = depth[curr]+1;
      q.push(out);
    }
  }
  for(int d = 1; d < MAX_D; d++) {
    for(int i = 1; i <= n; i++) {
      lca[d][i] = lca[d-1][lca[d-1][i]];
    }
  }
}

int main() {
  int q;
  scanf("%d%d", &n, &q);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &lca[0][i]);
    if(lca[0][i]) {
      children[lca[0][i]].push_back(i);
    }
    else {
      root = i;
    }
  }
  genMin();
  genLCA();
  genOrder();
  for(int i = 1; i <= n; i++) {
    avail.insert(i);
  }
  while(q--) solve();
}

Compilation message (stderr)

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
ballmachine.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
ballmachine.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &q);
   ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &lca[0][i]);
     ~~~~~^~~~~~~~~~~~~~~~~~

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