oj.uz

답안 #588676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588676 2022-07-03T20:30:55 Z MilosMilutinovic Ball Machine (BOI13_ballmachine) C++14
100 / 100
 258 ms 31876 KB 
/**
 *    author:  wxhtzdy
 *    created: 03.07.2022 19:51:50
**/
#include <bits/stdc++.h>

using namespace std;

template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, q;
  cin >> n >> q;
  vector<vector<int>> g(n);
  int root;
  for (int i = 0; i < n; i++) {
    int p;
    cin >> p;
    --p;
    if (p == -1) {
      root = i;
    } else {
      g[p].push_back(i);
    }
  }
  const int L = 20;
  vector<vector<int>> jump(n, vector<int>(L));
  vector<int> tin(n);
  vector<int> tout(n);
  vector<int> dep(n);
  vector<int> mn(n);
  int T = 0;
  function<void(int, int)> Dfs = [&](int v, int pr) {
    tin[v] = ++T;
    dep[v] = dep[pr] + 1;
    jump[v][0] = pr;
    mn[v] = v;
    for (int u : g[v]) {
      Dfs(u, v);
      mn[v] = min(mn[v], mn[u]);
    }
    tout[v] = ++T;
  };
  Dfs(root, root);
  for (int i = 0; i < n; i++) {
    sort(g[i].begin(), g[i].end(), [&](int x, int y) {
      return mn[x] < mn[y];
    });
  }
  vector<int> order(n);
  T = 0;
  Dfs = [&](int v, int pr) {
    order[v] = ++T;
    for (int u : g[v]) {
      if (u != pr) {
        Dfs(u, v);
      }
    }  
  };
  Dfs(root, root);                                           
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      jump[i][j] = jump[jump[i][j - 1]][j - 1];
    }
  }
  vector<int> deg(n);
  set<pair<int, int>> st;
  for (int i = 0; i < n; i++) {
    if (g[i].empty()) {
      st.emplace(order[i], i);
    }
  }
  fenwick<int> fenw(2 * (n + 1));      
  function<void(int, int)> Add = [&](int x, int v) {
    fenw.modify(tin[x], v);
    fenw.modify(tout[x], -v);
  };       
  function<void(int)> Ins = [&](int x) {
    deg[x] += 1;
    if (deg[x] == (int) g[x].size()) {
      st.emplace(order[x], x);
    }
  };
  function<void(int)> Del = [&](int x) {
    if (deg[x] == (int) g[x].size()) {
      st.erase(st.find(make_pair(order[x], x)));
    }
    deg[x] -= 1;
  };
  while (q--) {
    int op, x;
    cin >> op >> x;
    if (op == 1) {
      int ans;
      while (x--) {
        auto it = st.begin();
        int i = it->second;
        st.erase(it);
        Add(i, +1);
        if (i != root) {
          Ins(jump[i][0]);
        }
        ans = i;      
      }
      cout << ans + 1 << '\n';
    } else {
      --x;
      int cnt = fenw.get(tout[x]);
      cout << cnt << '\n';
      for (int i = L - 1; i >= 0; i--) {
        if (cnt >> i & 1) {
          x = jump[x][i];
        }
      }
      Add(x, -1);
      if (x != root) {
        Del(jump[x][0]);
      }  
      st.emplace(order[x], x);
    }
  }
  return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:129:26: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  129 |       cout << ans + 1 << '\n';
      |                          ^~~~
ballmachine.cpp:124:9: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |         if (i != root) {
      |         ^~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 164 ms 15436 KB Output is correct
3 Correct 65 ms 15528 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 7 ms 1172 KB Output is correct
10 Correct 24 ms 4052 KB Output is correct
11 Correct 158 ms 15416 KB Output is correct
12 Correct 76 ms 15520 KB Output is correct
13 Correct 117 ms 15448 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 6472 KB Output is correct
2 Correct 219 ms 27468 KB Output is correct
3 Correct 95 ms 22916 KB Output is correct
4 Correct 75 ms 8856 KB Output is correct
5 Correct 75 ms 8888 KB Output is correct
6 Correct 64 ms 8864 KB Output is correct
7 Correct 75 ms 7628 KB Output is correct
8 Correct 36 ms 6420 KB Output is correct
9 Correct 213 ms 27264 KB Output is correct
10 Correct 208 ms 27416 KB Output is correct
11 Correct 151 ms 27452 KB Output is correct
12 Correct 186 ms 24524 KB Output is correct
13 Correct 106 ms 28056 KB Output is correct
14 Correct 98 ms 22856 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 13888 KB Output is correct
2 Correct 239 ms 25264 KB Output is correct
3 Correct 133 ms 25268 KB Output is correct
4 Correct 137 ms 21756 KB Output is correct
5 Correct 155 ms 21896 KB Output is correct
6 Correct 144 ms 21968 KB Output is correct
7 Correct 134 ms 20164 KB Output is correct
8 Correct 129 ms 25320 KB Output is correct
9 Correct 233 ms 27436 KB Output is correct
10 Correct 258 ms 27572 KB Output is correct
11 Correct 241 ms 27596 KB Output is correct
12 Correct 236 ms 25280 KB Output is correct
13 Correct 225 ms 31876 KB Output is correct
14 Correct 193 ms 23356 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 27596 KB Output is correct
2 Correct 217 ms 25308 KB Output is correct
3 Correct 119 ms 31508 KB Output is correct
4 Correct 226 ms 27596 KB Output is correct
5 Correct 213 ms 27596 KB Output is correct
6 Correct 175 ms 27580 KB Output is correct
7 Correct 217 ms 25252 KB Output is correct
8 Correct 115 ms 31632 KB Output is correct
9 Correct 96 ms 22980 KB Output is correct