oj.uz

Submission #643435

# Submission time Handle Problem Language Result Execution time Memory
643435 2022-09-22T03:23:29 Z christinelynn Ball Machine (BOI13_ballmachine) C++17
100 / 100
 170 ms 33148 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 88 ms 16256 KB Output is correct
3 Correct 53 ms 16556 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 5 ms 3540 KB Output is correct
10 Correct 15 ms 6100 KB Output is correct
11 Correct 94 ms 16264 KB Output is correct
12 Correct 54 ms 16528 KB Output is correct
13 Correct 77 ms 16280 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8520 KB Output is correct
2 Correct 150 ms 27684 KB Output is correct
3 Correct 65 ms 23260 KB Output is correct
4 Correct 50 ms 10492 KB Output is correct
5 Correct 52 ms 10300 KB Output is correct
6 Correct 51 ms 10348 KB Output is correct
7 Correct 47 ms 9264 KB Output is correct
8 Correct 28 ms 8560 KB Output is correct
9 Correct 129 ms 28168 KB Output is correct
10 Correct 144 ms 27760 KB Output is correct
11 Correct 142 ms 27732 KB Output is correct
12 Correct 125 ms 25260 KB Output is correct
13 Correct 98 ms 29348 KB Output is correct
14 Correct 66 ms 23268 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 15600 KB Output is correct
2 Correct 149 ms 25952 KB Output is correct
3 Correct 104 ms 26896 KB Output is correct
4 Correct 112 ms 23240 KB Output is correct
5 Correct 103 ms 22828 KB Output is correct
6 Correct 101 ms 22824 KB Output is correct
7 Correct 95 ms 21220 KB Output is correct
8 Correct 105 ms 26952 KB Output is correct
9 Correct 145 ms 28356 KB Output is correct
10 Correct 155 ms 27848 KB Output is correct
11 Correct 148 ms 27876 KB Output is correct
12 Correct 154 ms 25924 KB Output is correct
13 Correct 160 ms 33148 KB Output is correct
14 Correct 92 ms 23272 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 28356 KB Output is correct
2 Correct 158 ms 25992 KB Output is correct
3 Correct 113 ms 32904 KB Output is correct
4 Correct 138 ms 28436 KB Output is correct
5 Correct 170 ms 27912 KB Output is correct
6 Correct 123 ms 27800 KB Output is correct
7 Correct 153 ms 25928 KB Output is correct
8 Correct 101 ms 32900 KB Output is correct
9 Correct 69 ms 23288 KB Output is correct