oj.uz

답안 #231761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
231761 2020-05-14T15:51:03 Z border Ball Machine (BOI13_ballmachine) C++14
100 / 100
 233 ms 28348 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++)
        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(0, root);
  dfs(0, 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 (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:60: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:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~
ballmachine.cpp:72: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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 132 ms 13176 KB Output is correct
3 Correct 92 ms 13048 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 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 12 ms 3328 KB Output is correct
10 Correct 30 ms 5248 KB Output is correct
11 Correct 130 ms 13176 KB Output is correct
12 Correct 85 ms 13048 KB Output is correct
13 Correct 122 ms 13176 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 7416 KB Output is correct
2 Correct 172 ms 22776 KB Output is correct
3 Correct 108 ms 17908 KB Output is correct
4 Correct 76 ms 8952 KB Output is correct
5 Correct 78 ms 8824 KB Output is correct
6 Correct 71 ms 8824 KB Output is correct
7 Correct 71 ms 7800 KB Output is correct
8 Correct 46 ms 7544 KB Output is correct
9 Correct 165 ms 23160 KB Output is correct
10 Correct 166 ms 22776 KB Output is correct
11 Correct 170 ms 22776 KB Output is correct
12 Correct 182 ms 20472 KB Output is correct
13 Correct 129 ms 24952 KB Output is correct
14 Correct 120 ms 17908 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 13048 KB Output is correct
2 Correct 207 ms 21112 KB Output is correct
3 Correct 140 ms 23160 KB Output is correct
4 Correct 145 ms 19192 KB Output is correct
5 Correct 137 ms 18808 KB Output is correct
6 Correct 135 ms 18936 KB Output is correct
7 Correct 135 ms 17276 KB Output is correct
8 Correct 148 ms 23160 KB Output is correct
9 Correct 226 ms 23416 KB Output is correct
10 Correct 214 ms 23032 KB Output is correct
11 Correct 201 ms 23032 KB Output is correct
12 Correct 218 ms 20984 KB Output is correct
13 Correct 233 ms 28348 KB Output is correct
14 Correct 174 ms 18292 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 23544 KB Output is correct
2 Correct 222 ms 20984 KB Output is correct
3 Correct 146 ms 27768 KB Output is correct
4 Correct 199 ms 23544 KB Output is correct
5 Correct 215 ms 23032 KB Output is correct
6 Correct 178 ms 23032 KB Output is correct
7 Correct 205 ms 21112 KB Output is correct
8 Correct 156 ms 27768 KB Output is correct
9 Correct 112 ms 17908 KB Output is correct