oj.uz

Submission #231507

# Submission time Handle Problem Language Result Execution time Memory
231507 2020-05-13T21:02:40 Z border Ball Machine (BOI13_ballmachine) C++14
0 / 100
 1000 ms 31216 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][24], L[N], rev[N], val[N];
vector<int> adj[N];
ordered_set s;

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);
  }
  rev[ptr] = u;
  val[u] = ptr;
  s.insert({ptr++, u});
}

void init() {
  int i, j;
  for (i = 1; i <= n; i++)
    for (j = 0; 1 << j < n; j++)
      P[i][j] = -1;
  for (i = 1; i <= n; i++)
    P[i][0] = T[i];
  for (j = 1; 1 << j < n; j++)
    for (i = 1; i <= n; i++)
      if (P[i][j - 1] != -1)
        P[i][j] = P[P[i][j - 1]][j - 1];
}

int klevpar(int u, int k) {
  int log, i;
  for (log = 1; 1 << log <= L[u]; log++);
  log--;
  for (i = log; i >= 0; i--)
    if (L[u] - (1 << i) >= k)
      u = P[u][i];
  
  return u;
}

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);
  }
  for (int i = 0; i <= n; ++i) sort(all(adj[i]));
  dfs(-1, root, 0);
  init();
  vector<pair<int, int>> er;
  while (q--) {
    int ty, v;
    scanf("%d %d", &ty, &v);
    if (ty == 1) {
      int ret = (*s.find_by_order(v - 1)).ss;
      printf("%d\n", ret);
      er.clear();
      for (int i = 0; i < v; ++i) er.push_back(*s.find_by_order(i));
      for (auto p: er) s.erase(p);
    }
    else {
      int ret = 0;
      for (int lev = 0; lev < L[v]; ++lev) {
        int u = klevpar(v, lev);
        if (s.find({val[u], u}) == s.end()) {
          s.insert({val[u], u});
          ret = L[v] - lev;
          break;
        }
      }
      printf("%d\n", ret);
    }
  }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:62: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:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~
ballmachine.cpp:75: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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB Output isn't correct
2 Incorrect 309 ms 16632 KB Output isn't correct
3 Incorrect 194 ms 16376 KB Output isn't correct
4 Incorrect 6 ms 2688 KB Output isn't correct
5 Incorrect 6 ms 2688 KB Output isn't correct
6 Incorrect 7 ms 2944 KB Output isn't correct
7 Incorrect 7 ms 2944 KB Output isn't correct
8 Incorrect 7 ms 2944 KB Output isn't correct
9 Incorrect 20 ms 3584 KB Output isn't correct
10 Incorrect 55 ms 6272 KB Output isn't correct
11 Incorrect 312 ms 17012 KB Output isn't correct
12 Incorrect 195 ms 16380 KB Output isn't correct
13 Incorrect 270 ms 16504 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 7808 KB Time limit exceeded
2 Execution timed out 1093 ms 26104 KB Time limit exceeded
3 Incorrect 183 ms 22644 KB Output isn't correct
4 Execution timed out 1093 ms 10488 KB Time limit exceeded
5 Execution timed out 1095 ms 9848 KB Time limit exceeded
6 Execution timed out 1091 ms 9848 KB Time limit exceeded
7 Execution timed out 1090 ms 9212 KB Time limit exceeded
8 Execution timed out 1089 ms 7808 KB Time limit exceeded
9 Execution timed out 1088 ms 26232 KB Time limit exceeded
10 Execution timed out 1095 ms 26104 KB Time limit exceeded
11 Execution timed out 1095 ms 25848 KB Time limit exceeded
12 Execution timed out 1098 ms 23928 KB Time limit exceeded
13 Execution timed out 1095 ms 26872 KB Time limit exceeded
14 Incorrect 180 ms 22644 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 15344 KB Time limit exceeded
2 Execution timed out 1084 ms 25328 KB Time limit exceeded
3 Execution timed out 1098 ms 25208 KB Time limit exceeded
4 Execution timed out 1094 ms 22180 KB Time limit exceeded
5 Execution timed out 1091 ms 21880 KB Time limit exceeded
6 Execution timed out 1092 ms 21752 KB Time limit exceeded
7 Execution timed out 1084 ms 20600 KB Time limit exceeded
8 Execution timed out 1093 ms 25336 KB Time limit exceeded
9 Execution timed out 1096 ms 27500 KB Time limit exceeded
10 Execution timed out 1096 ms 26864 KB Time limit exceeded
11 Execution timed out 1093 ms 26864 KB Time limit exceeded
12 Execution timed out 1098 ms 25456 KB Time limit exceeded
13 Execution timed out 1095 ms 31216 KB Time limit exceeded
14 Incorrect 212 ms 23788 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 26200 KB Time limit exceeded
2 Execution timed out 1098 ms 25328 KB Time limit exceeded
3 Execution timed out 1097 ms 30120 KB Time limit exceeded
4 Execution timed out 1098 ms 26232 KB Time limit exceeded
5 Execution timed out 1096 ms 26356 KB Time limit exceeded
6 Execution timed out 1095 ms 25720 KB Time limit exceeded
7 Execution timed out 1094 ms 25328 KB Time limit exceeded
8 Execution timed out 1101 ms 29944 KB Time limit exceeded
9 Incorrect 192 ms 22644 KB Output isn't correct