oj.uz

답안 #231733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
231733 2020-05-14T14:49:41 Z border Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 227 ms 131076 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; j < 18; j++)
      P[i][j] = -1;
  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, 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 (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: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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 81 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 89 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 91 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 78 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 78 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 78 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 78 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 77 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 74 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 79 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 96 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 92 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 96 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 7804 KB Output is correct
2 Runtime error 104 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 98 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 82 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 85 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Incorrect 77 ms 9336 KB Output isn't correct
7 Runtime error 85 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Correct 48 ms 7928 KB Output is correct
9 Runtime error 99 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 104 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Incorrect 153 ms 23288 KB Output isn't correct
12 Runtime error 110 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Correct 116 ms 25208 KB Output is correct
14 Runtime error 99 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 90 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 106 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 130 ms 23416 KB Output is correct
4 Runtime error 102 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 99 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 101 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 98 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Correct 140 ms 23416 KB Output is correct
9 Runtime error 102 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Incorrect 218 ms 23416 KB Output isn't correct
11 Incorrect 227 ms 23524 KB Output isn't correct
12 Runtime error 111 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Correct 221 ms 28664 KB Output is correct
14 Runtime error 101 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 97 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 104 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 134 ms 28280 KB Output is correct
4 Runtime error 104 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Incorrect 204 ms 23416 KB Output isn't correct
6 Runtime error 101 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 109 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Correct 141 ms 28280 KB Output is correct
9 Runtime error 100 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)