oj.uz

Submission #231758

# Submission time Handle Problem Language Result Execution time Memory
231758 2020-05-14T15:40:05 Z border Ball Machine (BOI13_ballmachine) C++14
77.381 / 100
 273 ms 28664 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, q, ptr, root;
int T[N], P[N][20], L[N], col[N], val[N], sub[N];
vector<int> adj[N];
set<pair<int, int>> s;
 
bool cmp(int A, int B) {
  return sub[A] < sub[B];
}
 
void dfs0(int from, int u) {
  sub[u] = u;
  for (auto v: adj[u]) {
    if (v == from) continue;
    dfs0(u, v);
    sub[u] = min(sub[u], sub[v]);
  }
  sort(all(adj[u]), cmp);
}
 
void dfs(int from, int u, int dep) {
  T[u] = from;
  L[u] = dep;
  for (auto v: adj[u]){
    if (v == from) continue;
    dfs(u, v, dep + 1);
  }
  val[u] = ptr;
  s.insert({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, &q);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    if (x == 0) root = i;
    adj[x].push_back(i);
  }
  dfs0(-1, root);
  dfs(-1, root, 0);
  init();
  while (q--) {
    int ty, v;
    scanf("%d %d", &ty, &v);
    if (ty == 1) {
      int ret;
      while (v--) {
        int node = (*s.begin()).ss;
        col[node] = 1;
        ret = node;
        s.erase({val[node], node});
      }
      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;
      s.insert({val[v], v});
      printf("%d\n", ret);
    }
  }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:61: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:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~
ballmachine.cpp:73: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 6 ms 2688 KB Output is correct
2 Correct 140 ms 13432 KB Output is correct
3 Correct 91 ms 13304 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Correct 13 ms 3328 KB Output is correct
10 Correct 29 ms 5376 KB Output is correct
11 Correct 144 ms 13432 KB Output is correct
12 Correct 101 ms 13432 KB Output is correct
13 Correct 136 ms 13348 KB Output is correct

Subtask #2
27.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7672 KB Output is correct
2 Correct 193 ms 23160 KB Output is correct
3 Correct 112 ms 18332 KB Output is correct
4 Correct 83 ms 9080 KB Output is correct
5 Correct 87 ms 8952 KB Output is correct
6 Correct 76 ms 8952 KB Output is correct
7 Correct 78 ms 7928 KB Output is correct
8 Correct 49 ms 7544 KB Output is correct
9 Incorrect 206 ms 23928 KB Output isn't correct
10 Correct 195 ms 23160 KB Output is correct
11 Correct 180 ms 23292 KB Output is correct
12 Correct 168 ms 20856 KB Output is correct
13 Correct 141 ms 25184 KB Output is correct
14 Correct 125 ms 18292 KB Output is correct

Subtask #3
22.8571428571 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 13304 KB Output is correct
2 Incorrect 243 ms 21368 KB Output isn't correct
3 Correct 141 ms 23416 KB Output is correct
4 Correct 148 ms 19580 KB Output is correct
5 Correct 143 ms 19168 KB Output is correct
6 Correct 140 ms 19192 KB Output is correct
7 Correct 143 ms 17532 KB Output is correct
8 Correct 150 ms 23416 KB Output is correct
9 Correct 262 ms 23928 KB Output is correct
10 Incorrect 273 ms 23416 KB Output isn't correct
11 Incorrect 229 ms 23416 KB Output isn't correct
12 Incorrect 236 ms 21484 KB Output isn't correct
13 Incorrect 254 ms 28664 KB Output isn't correct
14 Incorrect 185 ms 18804 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 23856 KB Output isn't correct
2 Incorrect 215 ms 21368 KB Output isn't correct
3 Correct 149 ms 28280 KB Output is correct
4 Incorrect 246 ms 24056 KB Output isn't correct
5 Incorrect 216 ms 23416 KB Output isn't correct
6 Correct 172 ms 23288 KB Output is correct
7 Incorrect 227 ms 21432 KB Output isn't correct
8 Correct 153 ms 28152 KB Output is correct
9 Incorrect 126 ms 18548 KB Output isn't correct