Submission #643435

#	Time	Username	Problem	Language	Result	Execution time	Memory
643435		christinelynn	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	170 ms	33148 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > >
#define mikochi priority_queue<long long, vector<long long>, greater<long long> >

long long n, q, p[100069], tp, a[100069], od[100069], up[100069][17], pw[18], x, ti = 0, mn[100069], sn, pos[100069], li, cn, co, dp[100069], ans;
vector<long long> al[100069];
mikochi pq;

void dfs(long long cn) {
  long long i, j, nn;
  if (p[cn] == 0) {
    up[cn][0] = cn;
  } else {
    up[cn][0] = p[cn];
  }
  for (i=1; i<=16; i++) {
    up[cn][i] = up[up[cn][i-1]][i-1];
  }
  mn[cn] = cn;
  for (i=0; i<al[cn].size(); i++) {
    nn = al[cn][i];
    dp[nn] = dp[cn]+1;
    dfs(nn);
    mn[cn] = min(mn[cn], mn[nn]);
  }
}

void dfs1(long long cn) {
  long long i, j, nn;
  for (i=0; i<al[cn].size(); i++) {
    nn = al[cn][i];
    dfs1(nn);
  }
  od[cn] = ++ti;
  pos[od[cn]] = cn;
}

long long bl(long long cn) {
  long long i, j, cu, un;
  for (i=16; i>=0; i--) {
    un = up[cn][i];
    if (a[un] == 1) {
      cn = un;
    }
  }
  return cn;
}

bool cmp(long long x, long long y) {
  return mn[x]<mn[y];
}

int main() {
  nyahalo
  long long i, j;
  pw[0] = 1;
  for (i=1; i<=17; i++) {
    pw[i] = pw[i-1]*2;
  }
  cin >> n >> q;
  for (i=1; i<=n; i++) {
    a[i] = 0;
    cin >> p[i];
    if (p[i] != 0) {
      al[p[i]].push_back(i);
    } else {
      sn = i;
    }
  }
  ti = 0;
  dp[sn] = 0;
  dfs(sn);
  for (i=1; i<=n; i++) {
    pq.push(i);
    if (al[i].size()>0) {
      sort(al[i].begin(), al[i].end(), cmp);
    }
  }
  ti = 0;
  dfs1(sn);
  while (q--) {
    cin >> tp >> x;
    if (tp == 1) {
      for (i=1; i<=x; i++) {
        co = pq.top();
        pq.pop();
        cn = pos[co];
        a[cn] = 1;
        li = cn;
      }
      cout << li << "\n";
    } else {
      cn = bl(x);
      ans = dp[x]-dp[cn];
      cout << ans << "\n";
      a[cn] = 0;
      co = od[cn];
      pq.push(co);
    }  
  }
  otsumiko
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs(long long int)':
ballmachine.cpp:24:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for (i=0; i<al[cn].size(); i++) {
      |             ~^~~~~~~~~~~~~~
ballmachine.cpp:14:16: warning: unused variable 'j' [-Wunused-variable]
   14 |   long long i, j, nn;
      |                ^
ballmachine.cpp: In function 'void dfs1(long long int)':
ballmachine.cpp:34:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for (i=0; i<al[cn].size(); i++) {
      |             ~^~~~~~~~~~~~~~
ballmachine.cpp:33:16: warning: unused variable 'j' [-Wunused-variable]
   33 |   long long i, j, nn;
      |                ^
ballmachine.cpp: In function 'long long int bl(long long int)':
ballmachine.cpp:43:16: warning: unused variable 'j' [-Wunused-variable]
   43 |   long long i, j, cu, un;
      |                ^
ballmachine.cpp:43:19: warning: unused variable 'cu' [-Wunused-variable]
   43 |   long long i, j, cu, un;
      |                   ^~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:59:16: warning: unused variable 'j' [-Wunused-variable]
   59 |   long long i, j;
      |                ^

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