oj.uz

Submission #231757

# Submission time Handle Problem Language Result Execution time Memory
231757 2020-05-14T15:39:20 Z border Ball Machine (BOI13_ballmachine) C++14
100 / 100
 179 ms 35820 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 5120 KB Output is correct
2 Correct 113 ms 13812 KB Output is correct
3 Correct 85 ms 13812 KB Output is correct
4 Correct 8 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 12 ms 5632 KB Output is correct
10 Correct 26 ms 7296 KB Output is correct
11 Correct 104 ms 13940 KB Output is correct
12 Correct 80 ms 13812 KB Output is correct
13 Correct 95 ms 13900 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 10872 KB Output is correct
2 Correct 160 ms 26224 KB Output is correct
3 Correct 98 ms 18020 KB Output is correct
4 Correct 70 ms 11896 KB Output is correct
5 Correct 67 ms 11512 KB Output is correct
6 Correct 62 ms 11512 KB Output is correct
7 Correct 69 ms 10100 KB Output is correct
8 Correct 47 ms 10872 KB Output is correct
9 Correct 145 ms 26988 KB Output is correct
10 Correct 158 ms 26096 KB Output is correct
11 Correct 136 ms 26104 KB Output is correct
12 Correct 153 ms 22172 KB Output is correct
13 Correct 114 ms 31832 KB Output is correct
14 Correct 100 ms 18024 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 16116 KB Output is correct
2 Correct 157 ms 22764 KB Output is correct
3 Correct 121 ms 29564 KB Output is correct
4 Correct 107 ms 22768 KB Output is correct
5 Correct 106 ms 22004 KB Output is correct
6 Correct 112 ms 22000 KB Output is correct
7 Correct 110 ms 19164 KB Output is correct
8 Correct 129 ms 29680 KB Output is correct
9 Correct 151 ms 27116 KB Output is correct
10 Correct 172 ms 26224 KB Output is correct
11 Correct 164 ms 26348 KB Output is correct
12 Correct 163 ms 22772 KB Output is correct
13 Correct 179 ms 35820 KB Output is correct
14 Correct 121 ms 18536 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 27244 KB Output is correct
2 Correct 174 ms 22764 KB Output is correct
3 Correct 133 ms 35388 KB Output is correct
4 Correct 166 ms 27248 KB Output is correct
5 Correct 159 ms 26352 KB Output is correct
6 Correct 160 ms 26224 KB Output is correct
7 Correct 153 ms 22768 KB Output is correct
8 Correct 123 ms 35308 KB Output is correct
9 Correct 96 ms 18152 KB Output is correct