oj.uz

Submission #725643

# Submission time Handle Problem Language Result Execution time Memory
725643 2023-04-17T19:53:24 Z YENGOYAN Ball Machine (BOI13_ballmachine) C++14
100 / 100
 445 ms 41848 KB 
/*
                                    //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
                                    \\                                    //
                                    //  271828___182845__904523__53602__  \\
                                    \\  87___47____13______52____66__24_  //
                                    //  97___75____72______47____09___36  \\
                                    \\  999595_____74______96____69___67  //
                                    //  62___77____24______07____66__30_  \\
                                    \\  35___35____47______59____45713__  //
                                    //                                    \\
                                    \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <algorithm>
#include <bitset>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e18;

vector<int> dx = { 1, 0, 0, -1, 1, 1, -1, -1 };
vector<int> dy = { 0, 1, -1, 0, 1, -1, 1, -1 };

vector<int> ids;

struct func{
  bool operator()(const int a, const int b){
    return ids[a] < ids[b];
  }
};

void solve() {
  int n, q; cin >> n >> q;
  vector<int> par(n);
  vector<vector<int>> gp(n);
  vector<set<int>> to_check(n);
  ids = vector<int> (n);
  int root = 0;
  for(int i = 0; i < n ;++i){
    int p; cin >> p; --p;
    par[i] = p;
    if(p != -1) {
      gp[p].push_back(i);
      to_check[p].insert(i);
    }
    else root = i;
  }
  vector<int> col(n);
  vector<int> order, sub(n);
  set<int, func> to_col;
    vector<vector<int>> up(n, vector<int> (20));
  vector<int> d(n);
  function<void(int)> dfs = [&](int u){
    if(par[u] == -1) up[u][0] = u;
    else up[u][0] = par[u];
    sub[u] = u;
    for(int i = 1; i < 20; ++i){
      up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for(int &v : gp[u]){
      d[v] = d[u] + 1;
      dfs(v);
      sub[u] = min(sub[u], sub[v]);
    }
  };
  dfs(root);
  vector<vector<pair<int, int>>> new_gp(n);
  for(int i = 0; i < n; ++i){
    for(int &j : gp[i]){
      new_gp[i].push_back({sub[j], j});
    }
  }
  for(int i = 0; i < n; ++i){
    sort(new_gp[i].begin(), new_gp[i].end());
  }
  function<void(int)> get_order = [&](int u){
    for(pair<int, int> &v : new_gp[u]){
      get_order(v.second);
    }
    order.push_back(u);
  };
  get_order(root);
  for(int i = 0; i < n; ++i){
    ids[order[i]] = i;
  }
  function<int(int)> fnd = [&](int u){
    if(col[root]) {
      return root;
    }
    for(int i = 19; i >= 0; --i){
      if(col[up[u][i]]) {
        u = up[u][i];
      }
    }
    return u;
  };
  for(int i = 0; i < n; ++i) {
    if(gp[i].size() == 0 && i != root) {
      to_col.insert(i);
    }
  }
  while(q--){
    int tp; cin >> tp;
    if(tp == 1){
      int k, lst = 0; cin >> k;
      while(k-- && to_col.size()){
        int u = *to_col.begin();
        lst = u;
        col[u] = 1;
        to_col.erase(u);
        if(par[u] != -1){
          to_check[par[u]].erase(u);
          if(to_check[par[u]].size() == 0){
            to_col.insert(par[u]);
          }
        }
      }
      cout << ++lst << "\n";
    }
    else {
      int u; cin >> u; --u;
      int lst_black = fnd(u);
      cout << d[u] - d[lst_black] << "\n";
      col[lst_black] = 0;
      to_col.insert(lst_black);
      to_col.erase(par[lst_black]);
      if(par[lst_black] != -1) {
        to_check[par[lst_black]].insert(lst_black);
      }
    }
  }

}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  // int t; cin >> t; while(t--)
  solve();
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 238 ms 22564 KB Output is correct
3 Correct 118 ms 22764 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 672 KB Output is correct
9 Correct 10 ms 1620 KB Output is correct
10 Correct 49 ms 5856 KB Output is correct
11 Correct 247 ms 22560 KB Output is correct
12 Correct 107 ms 22740 KB Output is correct
13 Correct 176 ms 22600 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8256 KB Output is correct
2 Correct 375 ms 37740 KB Output is correct
3 Correct 158 ms 34624 KB Output is correct
4 Correct 127 ms 11816 KB Output is correct
5 Correct 181 ms 11708 KB Output is correct
6 Correct 151 ms 11680 KB Output is correct
7 Correct 163 ms 10348 KB Output is correct
8 Correct 50 ms 8216 KB Output is correct
9 Correct 383 ms 37992 KB Output is correct
10 Correct 405 ms 37752 KB Output is correct
11 Correct 305 ms 37636 KB Output is correct
12 Correct 434 ms 35320 KB Output is correct
13 Correct 183 ms 36868 KB Output is correct
14 Correct 151 ms 34636 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 19300 KB Output is correct
2 Correct 398 ms 36280 KB Output is correct
3 Correct 216 ms 33356 KB Output is correct
4 Correct 254 ms 30504 KB Output is correct
5 Correct 262 ms 30380 KB Output is correct
6 Correct 257 ms 30388 KB Output is correct
7 Correct 277 ms 28996 KB Output is correct
8 Correct 236 ms 33460 KB Output is correct
9 Correct 408 ms 38220 KB Output is correct
10 Correct 432 ms 37828 KB Output is correct
11 Correct 445 ms 37920 KB Output is correct
12 Correct 354 ms 36300 KB Output is correct
13 Correct 416 ms 41848 KB Output is correct
14 Correct 343 ms 34644 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 38236 KB Output is correct
2 Correct 417 ms 36424 KB Output is correct
3 Correct 207 ms 41620 KB Output is correct
4 Correct 413 ms 38352 KB Output is correct
5 Correct 427 ms 38016 KB Output is correct
6 Correct 312 ms 37788 KB Output is correct
7 Correct 366 ms 36328 KB Output is correct
8 Correct 224 ms 41676 KB Output is correct
9 Correct 140 ms 34748 KB Output is correct