oj.uz

Submission #102185

# Submission time Handle Problem Language Result Execution time Memory
102185 2019-03-23T10:14:47 Z WLZ Ball Machine (BOI13_ballmachine) C++17
45.5556 / 100
 1000 ms 33568 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 it = st.begin(); k > 0; it++, k--) {
        used[order[*it]] = 1;
        last = order[*it];
        st.erase(it);
      }
      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:70: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 3 ms 384 KB Output is correct
2 Correct 242 ms 14236 KB Output is correct
3 Correct 169 ms 14560 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 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 4 ms 512 KB Output is correct
9 Correct 14 ms 1152 KB Output is correct
10 Correct 44 ms 3800 KB Output is correct
11 Correct 292 ms 14240 KB Output is correct
12 Correct 153 ms 14540 KB Output is correct
13 Correct 172 ms 14108 KB Output is correct

Subtask #2
17.1428571429 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 7696 KB Output is correct
2 Execution timed out 1076 ms 25592 KB Time limit exceeded
3 Correct 176 ms 21064 KB Output is correct
4 Correct 352 ms 9448 KB Output is correct
5 Correct 858 ms 9232 KB Output is correct
6 Correct 780 ms 9508 KB Output is correct
7 Correct 363 ms 7428 KB Output is correct
8 Correct 515 ms 7580 KB Output is correct
9 Execution timed out 1074 ms 25004 KB Time limit exceeded
10 Execution timed out 1078 ms 25616 KB Time limit exceeded
11 Execution timed out 1080 ms 25776 KB Time limit exceeded
12 Execution timed out 1078 ms 20772 KB Time limit exceeded
13 Execution timed out 1078 ms 29704 KB Time limit exceeded
14 Correct 233 ms 21068 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 15304 KB Time limit exceeded
2 Execution timed out 1074 ms 21668 KB Time limit exceeded
3 Execution timed out 1061 ms 27124 KB Time limit exceeded
4 Execution timed out 1086 ms 20860 KB Time limit exceeded
5 Execution timed out 1079 ms 21280 KB Time limit exceeded
6 Execution timed out 1070 ms 21196 KB Time limit exceeded
7 Execution timed out 1077 ms 18868 KB Time limit exceeded
8 Execution timed out 1077 ms 27260 KB Time limit exceeded
9 Execution timed out 1059 ms 25288 KB Time limit exceeded
10 Execution timed out 1076 ms 25572 KB Time limit exceeded
11 Execution timed out 1080 ms 25796 KB Time limit exceeded
12 Execution timed out 1079 ms 21300 KB Time limit exceeded
13 Execution timed out 1080 ms 33460 KB Time limit exceeded
14 Correct 321 ms 21060 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 25152 KB Time limit exceeded
2 Execution timed out 1083 ms 21284 KB Time limit exceeded
3 Execution timed out 1057 ms 33568 KB Time limit exceeded
4 Execution timed out 1060 ms 25268 KB Time limit exceeded
5 Execution timed out 1072 ms 25880 KB Time limit exceeded
6 Execution timed out 1063 ms 25664 KB Time limit exceeded
7 Execution timed out 1066 ms 21328 KB Time limit exceeded
8 Execution timed out 1073 ms 33484 KB Time limit exceeded
9 Correct 179 ms 21060 KB Output is correct