oj.uz

Submission #102183

# Submission time Handle Problem Language Result Execution time Memory
102183 2019-03-23T10:02:04 Z WLZ Ball Machine (BOI13_ballmachine) C++17
28.5165 / 100
 1000 ms 33648 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> p, order, depth, pos;
vector< vector<int> > children, up;
vector<int> used;
int root, cnt, max_log;

pair<int, vector<int> > dfs(int u, int par, int d) {
  int mn = u;
  depth[u] = d;
  vector< pair<int, vector<int> > > tmp;
  up[u][0] = par;
  for (int i = 1; i <= max_log; i++) {
    up[u][i] = up[up[u][i - 1]][i - 1];
  }
  for (auto v : children[u]) {
    tmp.push_back(dfs(v, u, d + 1));
    mn = min(mn, tmp.back().first);
  }
  sort(tmp.begin(), tmp.end());
  vector<int> ans;
  for (auto& v : tmp) {
    for (auto& x : v.second) {
      ans.push_back(x);
    }
  }
  ans.push_back(u);
  return {mn, ans};
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  max_log = (int) ceil(log2((double) n));
  up.assign(n + 1, vector<int>(max_log + 1));
  p.resize(n + 1);
  children.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    if (p[i] == 0) {
      root = i;
    } else {
      children[p[i]].push_back(i);
    }
  }
  depth.resize(n + 1);
  pos.resize(n + 1);
  order = dfs(root, root, 0).second;
  for (int i = 0; i < n; i++) {
    pos[order[i]] = i;
  }
  used.assign(n + 1, 0);
  set<int> st;
  for (int i = 1; i <= n; i++) {
    st.insert(pos[i]);
  }
  while (q--) {
    int type, k;
    cin >> type >> k;
    if (type == 1) {
      int last;
      set<int> newSt;
      for (auto& x : st) {
        if (k == 0) {
          newSt.insert(x);
        } else {
          k--;
          used[order[x]] = 1;
          last = order[x];  
        }
      }
      st = newSt;
      cout << last << '\n';
    } else {
      int oldK = k;
      for (int i = max_log; i >= 0; i--) {
        if (used[up[k][i]]) {
          k = up[k][i];
        }
      }
      used[k] = 0;
      st.insert(pos[k]);
      cout << depth[oldK] - depth[k] << '\n';
    }
  }
  return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:76:23: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
       cout << last << '\n';
                       ^~~~

Subtask #1
19.2307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 341 ms 16412 KB Output is correct
3 Execution timed out 1072 ms 16992 KB Time limit exceeded
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 11 ms 1280 KB Output is correct
10 Correct 44 ms 4432 KB Output is correct
11 Correct 336 ms 16020 KB Output is correct
12 Execution timed out 1064 ms 16988 KB Time limit exceeded
13 Execution timed out 1078 ms 16956 KB Time limit exceeded

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 8460 KB Time limit exceeded
2 Execution timed out 1072 ms 26136 KB Time limit exceeded
3 Execution timed out 1076 ms 25572 KB Time limit exceeded
4 Correct 331 ms 9820 KB Output is correct
5 Correct 831 ms 10656 KB Output is correct
6 Execution timed out 1071 ms 10656 KB Time limit exceeded
7 Correct 386 ms 8568 KB Output is correct
8 Execution timed out 1051 ms 8396 KB Time limit exceeded
9 Execution timed out 1076 ms 25084 KB Time limit exceeded
10 Execution timed out 1070 ms 25656 KB Time limit exceeded
11 Execution timed out 1071 ms 25888 KB Time limit exceeded
12 Execution timed out 1076 ms 20712 KB Time limit exceeded
13 Execution timed out 1075 ms 29692 KB Time limit exceeded
14 Execution timed out 1069 ms 25544 KB Time limit exceeded

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1050 ms 15332 KB Time limit exceeded
2 Execution timed out 1083 ms 21160 KB Time limit exceeded
3 Execution timed out 1081 ms 27024 KB Time limit exceeded
4 Execution timed out 1075 ms 20436 KB Time limit exceeded
5 Execution timed out 1078 ms 20772 KB Time limit exceeded
6 Execution timed out 1088 ms 21108 KB Time limit exceeded
7 Execution timed out 1082 ms 17036 KB Time limit exceeded
8 Execution timed out 1076 ms 27144 KB Time limit exceeded
9 Execution timed out 1070 ms 25364 KB Time limit exceeded
10 Execution timed out 1077 ms 25624 KB Time limit exceeded
11 Execution timed out 1072 ms 25664 KB Time limit exceeded
12 Execution timed out 1086 ms 21120 KB Time limit exceeded
13 Execution timed out 1075 ms 33484 KB Time limit exceeded
14 Correct 312 ms 21084 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 25164 KB Time limit exceeded
2 Execution timed out 1074 ms 21416 KB Time limit exceeded
3 Execution timed out 1063 ms 33648 KB Time limit exceeded
4 Execution timed out 1078 ms 25224 KB Time limit exceeded
5 Execution timed out 1084 ms 25624 KB Time limit exceeded
6 Execution timed out 1076 ms 25652 KB Time limit exceeded
7 Execution timed out 1067 ms 21284 KB Time limit exceeded
8 Execution timed out 1068 ms 33420 KB Time limit exceeded
9 Execution timed out 1069 ms 25668 KB Time limit exceeded