oj.uz

Submission #559257

# Submission time Handle Problem Language Result Execution time Memory
559257 2022-05-09T14:43:37 Z Sam_a17 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 475 ms 31908 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
// #include "temp.cpp"
#include <cstdio>
using namespace std;

#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif

#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) x.clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount

#define pb push_back
#define pf push_front
#define popf pop_front
#define popb pop_back

void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}

template <class T> void print(set <T> v);
template <class T> void print(vector <T> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T, class V> void print(pair <T, V> p);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque<T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(unordered_map<T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'

// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};

// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();

  if (str != "" && str != "input") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }

  if(str == "input") {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 1e5 + 10, inf = 1e9, LOG = 22;
int n, q, root = -1, mini[N], sit[N], up[N][LOG];
vector<int> adj[N], order;
set<pair<int, int>> st;

int dfsMin(int node, int parent) {
  mini[node] = node;
  for(auto u: adj[node]) {
    if(u == parent) continue;

    up[u][0] = node;
    for(int i = 1; i < LOG; i++) {
      up[u][i] = up[up[u][i - 1]][i - 1];
    }

    mini[node] = min(mini[node], dfsMin(u, node));
  }
  return mini[node];
}

void dfsOrder(int node, int parent) {
  vector<pair<int, int>> children;
  for(auto u: adj[node]) {
    if(u == parent) continue;
    children.emplace_back(mini[u], u);
  }

  sort(all(children));

  for(auto u: children) {
    dfsOrder(u.second, node);
  }

  order.push_back(node);
}

pair<int, int> findAncestor(int node) {
  int answ = 0;
  for(int i = LOG - 1; i >= 0; i--) {
    if(up[node][i] && st.find({sit[up[node][i]], up[node][i]}) == st.end()) {
      node = up[node][i];
      answ |= (1 << i);
    }
  }

  return {node, answ};
}

void solve_() {
  cin >> n >> q;
  for(int i = 1; i <= n; i++) {
    int parent; cin >> parent;
    if(!parent) {
      root = i;
      continue;
    }

    adj[i].push_back(parent);
    adj[parent].push_back(i);

    mini[i] = inf;
  }

  dfsMin(root, root);

  dfsOrder(root, root);

//  seg.upd(0, 1, 1);

  for(int i = 0; i < n; i++) {
    sit[order[i]] = i + 1;
    st.insert({i + 1, order[i]});
  }

  while(q--) {
    int type, a; cin >> type >> a;
    if(type == 1) {
      int lst = -1;
      while(a--) {
        lst = st.begin()->second;
        st.erase(st.begin());
      }
      printf("%d\n", lst);
    } else {
      auto ans = findAncestor(a);
      st.insert({sit[ans.first], ans.first});
      printf("%d\n", ans.second);
    }
  }
}

int main() {
  setIO();

  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };

  int test_cases = 1;
  solve(test_cases);

  return 0;
}

Compilation message

ballmachine.cpp: In function 'void setIO(std::string)':
ballmachine.cpp:66:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:72:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 182 ms 14532 KB Output is correct
3 Correct 104 ms 14592 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 4 ms 2764 KB Output is correct
8 Correct 4 ms 2772 KB Output is correct
9 Correct 12 ms 3412 KB Output is correct
10 Correct 34 ms 5600 KB Output is correct
11 Correct 187 ms 14652 KB Output is correct
12 Correct 120 ms 14580 KB Output is correct
13 Correct 151 ms 14472 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8112 KB Output is correct
2 Correct 475 ms 26068 KB Output is correct
3 Correct 135 ms 20632 KB Output is correct
4 Correct 144 ms 9676 KB Output is correct
5 Correct 199 ms 9756 KB Output is correct
6 Correct 185 ms 9768 KB Output is correct
7 Correct 194 ms 8476 KB Output is correct
8 Correct 64 ms 8120 KB Output is correct
9 Correct 312 ms 26008 KB Output is correct
10 Correct 410 ms 26068 KB Output is correct
11 Correct 369 ms 26068 KB Output is correct
12 Correct 380 ms 22820 KB Output is correct
13 Correct 204 ms 28380 KB Output is correct
14 Correct 124 ms 20596 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 14360 KB Output is correct
2 Correct 470 ms 23468 KB Output is correct
3 Correct 316 ms 26016 KB Output is correct
4 Correct 230 ms 21520 KB Output is correct
5 Correct 265 ms 21580 KB Output is correct
6 Correct 290 ms 21536 KB Output is correct
7 Correct 221 ms 19272 KB Output is correct
8 Correct 261 ms 25996 KB Output is correct
9 Correct 298 ms 26340 KB Output is correct
10 Correct 353 ms 26264 KB Output is correct
11 Correct 360 ms 26164 KB Output is correct
12 Correct 340 ms 23428 KB Output is correct
13 Correct 381 ms 31908 KB Output is correct
14 Correct 158 ms 20632 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 26364 KB Output is correct
2 Correct 351 ms 23336 KB Output is correct
3 Correct 186 ms 31700 KB Output is correct
4 Correct 285 ms 26264 KB Output is correct
5 Correct 372 ms 26196 KB Output is correct
6 Correct 314 ms 26228 KB Output is correct
7 Correct 341 ms 23432 KB Output is correct
8 Correct 190 ms 31672 KB Output is correct
9 Correct 111 ms 20560 KB Output is correct