oj.uz

Submission #102184

# Submission time Handle Problem Language Result Execution time Memory
102184 2019-03-23T10:04:33 Z WLZ Ball Machine (BOI13_ballmachine) C++17
45.5556 / 100
 1000 ms 33536 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) {
        k--;
        used[order[x]] = 1;
        last = order[x];
        st.erase(x);  
        if (k == 0) {
          break;
        }
      }
      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:75:23: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
       cout << last << '\n';
                       ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 250 ms 14144 KB Output is correct
3 Correct 142 ms 14560 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 484 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 14 ms 1152 KB Output is correct
10 Correct 44 ms 3792 KB Output is correct
11 Correct 293 ms 14104 KB Output is correct
12 Correct 150 ms 14480 KB Output is correct
13 Correct 200 ms 14140 KB Output is correct

Subtask #2
17.1428571429 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 7804 KB Output is correct
2 Execution timed out 1072 ms 25684 KB Time limit exceeded
3 Correct 228 ms 20980 KB Output is correct
4 Correct 379 ms 9644 KB Output is correct
5 Correct 945 ms 9484 KB Output is correct
6 Correct 885 ms 9324 KB Output is correct
7 Correct 354 ms 7488 KB Output is correct
8 Correct 519 ms 7636 KB Output is correct
9 Execution timed out 1064 ms 25064 KB Time limit exceeded
10 Execution timed out 1070 ms 25536 KB Time limit exceeded
11 Execution timed out 1035 ms 25764 KB Time limit exceeded
12 Execution timed out 1081 ms 20712 KB Time limit exceeded
13 Execution timed out 1076 ms 30380 KB Time limit exceeded
14 Correct 203 ms 21192 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 15168 KB Time limit exceeded
2 Execution timed out 1071 ms 21068 KB Time limit exceeded
3 Execution timed out 1078 ms 26940 KB Time limit exceeded
4 Execution timed out 1072 ms 20384 KB Time limit exceeded
5 Execution timed out 1064 ms 20804 KB Time limit exceeded
6 Execution timed out 1071 ms 20836 KB Time limit exceeded
7 Execution timed out 1064 ms 17096 KB Time limit exceeded
8 Execution timed out 1074 ms 27168 KB Time limit exceeded
9 Execution timed out 1067 ms 25248 KB Time limit exceeded
10 Execution timed out 1055 ms 25680 KB Time limit exceeded
11 Execution timed out 1080 ms 25820 KB Time limit exceeded
12 Execution timed out 1067 ms 21484 KB Time limit exceeded
13 Execution timed out 1076 ms 33536 KB Time limit exceeded
14 Correct 301 ms 21188 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 25248 KB Time limit exceeded
2 Execution timed out 1065 ms 21076 KB Time limit exceeded
3 Execution timed out 1077 ms 33468 KB Time limit exceeded
4 Execution timed out 1078 ms 25128 KB Time limit exceeded
5 Execution timed out 1082 ms 25692 KB Time limit exceeded
6 Execution timed out 1070 ms 25708 KB Time limit exceeded
7 Execution timed out 1076 ms 21228 KB Time limit exceeded
8 Execution timed out 1063 ms 33488 KB Time limit exceeded
9 Correct 207 ms 21188 KB Output is correct