oj.uz

답안 #231527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
231527 2020-05-13T21:44:52 Z border Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 229 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], sub[N];
vector<int> adj[N];
set<pair<int, int>> s;

bool cmp(int A, int B) {
  return sub[A] < sub[B];
}

int dfs0(int from, int u) {
  sub[u] = u;
  for (auto v: adj[u]) {
    if (v == from) continue;
    sub[u] = min(sub[u], dfs0(u, 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 dfs0(int, int)':
ballmachine.cpp:36:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:64: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:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~
ballmachine.cpp:76: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 121 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 28 ms 5248 KB Output isn't correct
11 Incorrect 134 ms 13176 KB Output isn't correct
12 Incorrect 87 ms 13304 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 7544 KB Output is correct
2 Incorrect 193 ms 22968 KB Output isn't correct
3 Incorrect 106 ms 18420 KB Output isn't correct
4 Incorrect 74 ms 8952 KB Output isn't correct
5 Incorrect 76 ms 8952 KB Output isn't correct
6 Incorrect 77 ms 8952 KB Output isn't correct
7 Incorrect 74 ms 7928 KB Output isn't correct
8 Correct 48 ms 7416 KB Output is correct
9 Incorrect 156 ms 23288 KB Output isn't correct
10 Incorrect 177 ms 23032 KB Output isn't correct
11 Incorrect 154 ms 22904 KB Output isn't correct
12 Incorrect 168 ms 20600 KB Output isn't correct
13 Correct 116 ms 24824 KB Output is correct
14 Incorrect 106 ms 18420 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 13048 KB Output isn't correct
2 Incorrect 198 ms 21112 KB Output isn't correct
3 Correct 128 ms 23032 KB Output is correct
4 Incorrect 126 ms 19320 KB Output isn't correct
5 Incorrect 128 ms 18808 KB Output isn't correct
6 Incorrect 122 ms 18808 KB Output isn't correct
7 Incorrect 124 ms 17272 KB Output isn't correct
8 Correct 148 ms 23008 KB Output is correct
9 Incorrect 227 ms 23416 KB Output isn't correct
10 Incorrect 229 ms 23032 KB Output isn't correct
11 Incorrect 219 ms 23160 KB Output isn't correct
12 Incorrect 229 ms 21104 KB Output isn't correct
13 Correct 211 ms 28280 KB Output is correct
14 Incorrect 181 ms 18420 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 199 ms 23416 KB Output isn't correct
2 Incorrect 216 ms 20988 KB Output isn't correct
3 Correct 136 ms 27768 KB Output is correct
4 Incorrect 206 ms 23416 KB Output isn't correct
5 Incorrect 199 ms 22976 KB Output isn't correct
6 Incorrect 167 ms 22904 KB Output isn't correct
7 Incorrect 200 ms 20960 KB Output isn't correct
8 Correct 140 ms 27744 KB Output is correct
9 Incorrect 111 ms 18296 KB Output isn't correct