oj.uz

Submission #231756

# Submission time Handle Problem Language Result Execution time Memory
231756 2020-05-14T15:37:17 Z border Ball Machine (BOI13_ballmachine) C++14
100 / 100
 186 ms 35816 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
 
using namespace std;
// using namespace __gnu_pbds;
 
#define debug(s) cerr << #s << " = " << s << '\n'
#define all(v) (v).begin(), (v).end()
#define mem(a,val) memset(a, val, sizeof a)
 
#define ff first
#define ss second
typedef long long ll;
 
// typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
 
const int N = 100010;
 
int n, qu, ptr, root;
int T[N], P[N][20], L[N], col[N], val[N];
vector<int> adj[N], g[N];

struct dat {
  int va, node;
  bool operator < (const dat &a) const {
    return va > a.va;
  }
};
 
priority_queue<dat> pq;
 
int dfs0(int from, int u) {
  priority_queue<dat> q;
  for (auto v: g[u]) {
    if (v == from) continue;
    q.push({dfs0(u, v), v});
  }
  int ret = u;
  while (!q.empty()) {
    adj[u].push_back(q.top().node);
    ret = min(ret, q.top().va);
    q.pop();
  }
  return ret;
}
 
void dfs(int from, int u) {
  T[u] = from;
  for (auto v: adj[u]) {
    if (v == from) continue;
    dfs(u, v);
  }
  val[u] = ptr;
  pq.push({ptr++, u});
}
 
void init() {
  int i, j;
  for (i = 1; i <= n; i++)
    P[i][0] = T[i];
  
  for (j = 1; j < 18; j++)
    for (i = 1; i <= n; i++)
      P[i][j] = P[P[i][j - 1]][j - 1];
}
 
 
int main() {
  scanf("%d %d", &n, &qu);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    if (x == 0) root = i;
    g[x].push_back(i);
  }
  dfs0(0, root);
  dfs(0, root);
  init();
  while (qu--) {
    int ty, v;
    scanf("%d %d", &ty, &v);
    if (ty == 1) {
      int ret;
      while (v--) {
        int curnode = pq.top().node;
        col[curnode] = 1;
        ret = curnode;
        pq.pop();
      }
      printf("%d\n", ret);
    }
    else {
      int ret = 0;
      for (int i = 16; i >= 0; --i) {
        if (col[P[v][i]]) {
          ret += (1 << i);
          v = P[v][i];
        }
      }
      col[v] = 0;
      pq.push({val[v], v});
      printf("%d\n", ret);
    }
  }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &qu);
   ~~~~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~
ballmachine.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &ty, &v);
     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 108 ms 14964 KB Output is correct
3 Correct 81 ms 14708 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 8 ms 5248 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 13 ms 5760 KB Output is correct
10 Correct 26 ms 7672 KB Output is correct
11 Correct 109 ms 15004 KB Output is correct
12 Correct 82 ms 14708 KB Output is correct
13 Correct 105 ms 14964 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 10872 KB Output is correct
2 Correct 155 ms 27372 KB Output is correct
3 Correct 103 ms 19044 KB Output is correct
4 Correct 70 ms 12536 KB Output is correct
5 Correct 64 ms 12280 KB Output is correct
6 Correct 65 ms 11512 KB Output is correct
7 Correct 66 ms 10868 KB Output is correct
8 Correct 46 ms 10872 KB Output is correct
9 Correct 157 ms 28272 KB Output is correct
10 Correct 149 ms 27504 KB Output is correct
11 Correct 151 ms 26096 KB Output is correct
12 Correct 144 ms 23532 KB Output is correct
13 Correct 116 ms 31856 KB Output is correct
14 Correct 112 ms 19044 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 16748 KB Output is correct
2 Correct 162 ms 24172 KB Output is correct
3 Correct 118 ms 29588 KB Output is correct
4 Correct 121 ms 23792 KB Output is correct
5 Correct 114 ms 22892 KB Output is correct
6 Correct 105 ms 22896 KB Output is correct
7 Correct 120 ms 20080 KB Output is correct
8 Correct 124 ms 29556 KB Output is correct
9 Correct 182 ms 28524 KB Output is correct
10 Correct 185 ms 26224 KB Output is correct
11 Correct 161 ms 26220 KB Output is correct
12 Correct 164 ms 24048 KB Output is correct
13 Correct 186 ms 35816 KB Output is correct
14 Correct 126 ms 19812 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 28524 KB Output is correct
2 Correct 157 ms 24048 KB Output is correct
3 Correct 139 ms 35308 KB Output is correct
4 Correct 183 ms 28528 KB Output is correct
5 Correct 181 ms 26348 KB Output is correct
6 Correct 147 ms 27500 KB Output is correct
7 Correct 164 ms 24048 KB Output is correct
8 Correct 138 ms 35308 KB Output is correct
9 Correct 99 ms 19176 KB Output is correct