oj.uz

답안 #231518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
231518 2020-05-13T21:32:27 Z border Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 209 ms 28280 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];
vector<int> adj[N];
set<pair<int, int>> 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);
  }
  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:51: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:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~
ballmachine.cpp:63: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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2688 KB Output isn't correct
2 Incorrect 131 ms 13176 KB Output isn't correct
3 Incorrect 100 ms 13432 KB Output isn't correct
4 Incorrect 6 ms 2688 KB Output isn't correct
5 Incorrect 7 ms 2816 KB Output isn't correct
6 Incorrect 7 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 135 ms 13176 KB Output isn't correct
12 Incorrect 90 ms 13432 KB Output isn't correct
13 Incorrect 109 ms 13176 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 7416 KB Output is correct
2 Incorrect 176 ms 22904 KB Output isn't correct
3 Incorrect 112 ms 18420 KB Output isn't correct
4 Incorrect 76 ms 8956 KB Output isn't correct
5 Incorrect 78 ms 8824 KB Output isn't correct
6 Incorrect 73 ms 8952 KB Output isn't correct
7 Incorrect 74 ms 7800 KB Output isn't correct
8 Correct 52 ms 7416 KB Output is correct
9 Incorrect 176 ms 23160 KB Output isn't correct
10 Incorrect 175 ms 23112 KB Output isn't correct
11 Incorrect 159 ms 22904 KB Output isn't correct
12 Incorrect 165 ms 20600 KB Output isn't correct
13 Correct 115 ms 24824 KB Output is correct
14 Incorrect 104 ms 18420 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 88 ms 13048 KB Output isn't correct
2 Incorrect 205 ms 21112 KB Output isn't correct
3 Correct 132 ms 23032 KB Output is correct
4 Incorrect 135 ms 19192 KB Output isn't correct
5 Incorrect 123 ms 19064 KB Output isn't correct
6 Incorrect 124 ms 18808 KB Output isn't correct
7 Incorrect 122 ms 17400 KB Output isn't correct
8 Correct 134 ms 23032 KB Output is correct
9 Incorrect 201 ms 23544 KB Output isn't correct
10 Incorrect 209 ms 22960 KB Output isn't correct
11 Incorrect 200 ms 23032 KB Output isn't correct
12 Incorrect 196 ms 21136 KB Output isn't correct
13 Correct 196 ms 28280 KB Output is correct
14 Incorrect 164 ms 18292 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 184 ms 23544 KB Output isn't correct
2 Incorrect 191 ms 21112 KB Output isn't correct
3 Correct 127 ms 27768 KB Output is correct
4 Incorrect 191 ms 23416 KB Output isn't correct
5 Incorrect 186 ms 23024 KB Output isn't correct
6 Incorrect 153 ms 22904 KB Output isn't correct
7 Incorrect 187 ms 20984 KB Output isn't correct
8 Correct 131 ms 27768 KB Output is correct
9 Incorrect 111 ms 18292 KB Output isn't correct