oj.uz

Submission #231529

# Submission time Handle Problem Language Result Execution time Memory
231529 2020-05-13T21:46:24 Z border Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 211 ms 28408 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(v, u);
    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++)
    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 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 = 1; i <= n; ++i) sort(all(adj[i]));
  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:65: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:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~
ballmachine.cpp:77: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 2816 KB Output isn't correct
2 Incorrect 123 ms 13176 KB Output isn't correct
3 Incorrect 87 ms 13304 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 6 ms 2816 KB Output isn't correct
7 Incorrect 7 ms 2816 KB Output isn't correct
8 Incorrect 7 ms 2816 KB Output isn't correct
9 Incorrect 13 ms 3328 KB Output isn't correct
10 Incorrect 29 ms 5248 KB Output isn't correct
11 Incorrect 130 ms 13176 KB Output isn't correct
12 Incorrect 88 ms 13304 KB Output isn't correct
13 Incorrect 111 ms 13168 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7544 KB Output is correct
2 Incorrect 177 ms 23032 KB Output isn't correct
3 Incorrect 104 ms 18420 KB Output isn't correct
4 Incorrect 78 ms 9080 KB Output isn't correct
5 Incorrect 86 ms 8824 KB Output isn't correct
6 Incorrect 76 ms 8824 KB Output isn't correct
7 Incorrect 76 ms 7800 KB Output isn't correct
8 Correct 49 ms 7544 KB Output is correct
9 Incorrect 163 ms 23372 KB Output isn't correct
10 Incorrect 183 ms 23096 KB Output isn't correct
11 Incorrect 149 ms 22904 KB Output isn't correct
12 Incorrect 180 ms 20600 KB Output isn't correct
13 Correct 114 ms 24876 KB Output is correct
14 Incorrect 108 ms 18604 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 13048 KB Output isn't correct
2 Incorrect 205 ms 21112 KB Output isn't correct
3 Correct 131 ms 23032 KB Output is correct
4 Incorrect 123 ms 19192 KB Output isn't correct
5 Incorrect 122 ms 18808 KB Output isn't correct
6 Incorrect 124 ms 18936 KB Output isn't correct
7 Incorrect 128 ms 17272 KB Output isn't correct
8 Correct 135 ms 23028 KB Output is correct
9 Incorrect 198 ms 23392 KB Output isn't correct
10 Incorrect 199 ms 23032 KB Output isn't correct
11 Incorrect 194 ms 23008 KB Output isn't correct
12 Incorrect 194 ms 20984 KB Output isn't correct
13 Correct 211 ms 28408 KB Output is correct
14 Incorrect 164 ms 18312 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 23416 KB Output isn't correct
2 Incorrect 193 ms 21132 KB Output isn't correct
3 Correct 139 ms 27768 KB Output is correct
4 Incorrect 180 ms 23544 KB Output isn't correct
5 Incorrect 179 ms 22904 KB Output isn't correct
6 Incorrect 154 ms 22904 KB Output isn't correct
7 Incorrect 189 ms 20984 KB Output isn't correct
8 Correct 128 ms 27768 KB Output is correct
9 Incorrect 104 ms 18420 KB Output isn't correct