oj.uz

Submission #102186

# Submission time Handle Problem Language Result Execution time Memory
102186 2019-03-23T10:17:59 Z WLZ Ball Machine (BOI13_ballmachine) C++17
45.5556 / 100
 1000 ms 34272 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;
      for (auto& x : order) {
        if (!used[x]) {
          used[x] = 1;
          last = x;
          k--;
          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 247 ms 14228 KB Output is correct
3 Correct 151 ms 14504 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 14 ms 1152 KB Output is correct
10 Correct 37 ms 3800 KB Output is correct
11 Correct 267 ms 14232 KB Output is correct
12 Correct 121 ms 14432 KB Output is correct
13 Correct 183 ms 14340 KB Output is correct

Subtask #2
17.1428571429 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 7684 KB Output is correct
2 Execution timed out 1076 ms 25832 KB Time limit exceeded
3 Correct 168 ms 21140 KB Output is correct
4 Correct 303 ms 9348 KB Output is correct
5 Correct 787 ms 9448 KB Output is correct
6 Correct 786 ms 9316 KB Output is correct
7 Correct 327 ms 7428 KB Output is correct
8 Correct 543 ms 7560 KB Output is correct
9 Execution timed out 1051 ms 24928 KB Time limit exceeded
10 Execution timed out 1064 ms 26260 KB Time limit exceeded
11 Execution timed out 1079 ms 25744 KB Time limit exceeded
12 Execution timed out 1076 ms 20704 KB Time limit exceeded
13 Execution timed out 1081 ms 29768 KB Time limit exceeded
14 Correct 156 ms 21064 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1012 ms 15284 KB Time limit exceeded
2 Execution timed out 1067 ms 21280 KB Time limit exceeded
3 Execution timed out 1061 ms 27628 KB Time limit exceeded
4 Execution timed out 1085 ms 20392 KB Time limit exceeded
5 Execution timed out 1087 ms 20740 KB Time limit exceeded
6 Execution timed out 1081 ms 20768 KB Time limit exceeded
7 Execution timed out 1080 ms 17180 KB Time limit exceeded
8 Execution timed out 1067 ms 27360 KB Time limit exceeded
9 Execution timed out 1085 ms 25164 KB Time limit exceeded
10 Execution timed out 1077 ms 25656 KB Time limit exceeded
11 Execution timed out 1076 ms 25772 KB Time limit exceeded
12 Execution timed out 1081 ms 21124 KB Time limit exceeded
13 Execution timed out 1075 ms 34272 KB Time limit exceeded
14 Correct 347 ms 21188 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 25164 KB Time limit exceeded
2 Execution timed out 1074 ms 21228 KB Time limit exceeded
3 Execution timed out 1088 ms 33352 KB Time limit exceeded
4 Execution timed out 1086 ms 25272 KB Time limit exceeded
5 Execution timed out 1073 ms 27252 KB Time limit exceeded
6 Execution timed out 1081 ms 27208 KB Time limit exceeded
7 Execution timed out 1089 ms 21316 KB Time limit exceeded
8 Execution timed out 1061 ms 33556 KB Time limit exceeded
9 Correct 155 ms 21064 KB Output is correct