oj.uz

Submission #231762

# Submission time Handle Problem Language Result Execution time Memory
231762 2020-05-14T15:52:37 Z border Ball Machine (BOI13_ballmachine) C++14
100 / 100
 239 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], 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) {
  T[u] = from;
  for (auto v: adj[u]){
    if (v == from) continue;
    dfs(u, v);
  }
  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++)
      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);
  }
  dfs0(-1, root);
  dfs(-1, root);
  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 (P[v][i] == -1) continue;
        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 7 ms 2688 KB Output is correct
2 Correct 134 ms 13176 KB Output is correct
3 Correct 89 ms 13048 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 6 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 32 ms 5248 KB Output is correct
11 Correct 137 ms 13176 KB Output is correct
12 Correct 91 ms 13048 KB Output is correct
13 Correct 123 ms 13176 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 7416 KB Output is correct
2 Correct 190 ms 22776 KB Output is correct
3 Correct 122 ms 17968 KB Output is correct
4 Correct 86 ms 8952 KB Output is correct
5 Correct 82 ms 8824 KB Output is correct
6 Correct 75 ms 8824 KB Output is correct
7 Correct 77 ms 7928 KB Output is correct
8 Correct 49 ms 7520 KB Output is correct
9 Correct 181 ms 23388 KB Output is correct
10 Correct 186 ms 22904 KB Output is correct
11 Correct 165 ms 22904 KB Output is correct
12 Correct 188 ms 20472 KB Output is correct
13 Correct 124 ms 24824 KB Output is correct
14 Correct 114 ms 17908 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 13028 KB Output is correct
2 Correct 227 ms 21096 KB Output is correct
3 Correct 150 ms 23032 KB Output is correct
4 Correct 139 ms 19296 KB Output is correct
5 Correct 137 ms 18808 KB Output is correct
6 Correct 137 ms 18808 KB Output is correct
7 Correct 130 ms 17272 KB Output is correct
8 Correct 154 ms 23032 KB Output is correct
9 Correct 210 ms 23416 KB Output is correct
10 Correct 212 ms 23032 KB Output is correct
11 Correct 216 ms 23032 KB Output is correct
12 Correct 214 ms 20984 KB Output is correct
13 Correct 239 ms 28408 KB Output is correct
14 Correct 183 ms 18420 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 23496 KB Output is correct
2 Correct 206 ms 21112 KB Output is correct
3 Correct 142 ms 27768 KB Output is correct
4 Correct 219 ms 23544 KB Output is correct
5 Correct 206 ms 23288 KB Output is correct
6 Correct 170 ms 23100 KB Output is correct
7 Correct 199 ms 20984 KB Output is correct
8 Correct 153 ms 27768 KB Output is correct
9 Correct 121 ms 17976 KB Output is correct