oj.uz

Submission #659591

# Submission time Handle Problem Language Result Execution time Memory
659591 2022-11-18T17:28:21 Z Filya Ball Machine (BOI13_ballmachine) C++17
100 / 100
 178 ms 27316 KB 
/////////////////////include/////////////////////
//#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <set>
#include <map>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stdio.h>
#include <climits>
#include <numeric>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T>
//using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/////////////////////define/////////////////////
#define ci(x) if(x) cout << "YES" << '\n'; else cout << "NO" << '\n';
#define cii(x) if(check(x))
#define MOD 1000000007
#define MOD2 998244353
#define oo 1e9
#define ool 1e18L
#define pii pair<int, int>
#define pll pair<long long, long long>
#define mii map<int, int>
#define vi vector<int>
#define vpi vector<pair<int, int>>
#define vll vector <ll>
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define alll(x) (x), (x) + n
#define clr(x) (x).clear();
#define fri(x) for(int i = 0; i < x; ++i)
#define frj(x) for(int j = 0; j < x; ++j)
#define frp(x) for(int p = 0; p < x; ++p)
#define frr(a, b) for(int i = a; i < b; ++i)
#define frrj(a, b) for(int j = a; j < b; ++j)
#define fra(x) for(int i = 0; i < x; ++i) cin >> a[i];
#define frb(x) for(int i = 0; i < x; ++i) cin >> b[i];
#define frs(x) for(auto it = x.begin(); it != x.end(); ++it)
#define fr(x) for(auto it : x) //el
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define dbg(x) cerr << #x << ": " << x << endl;
#define ce(x) cout << x << endl;
#define uniq(x) x.resize(unique(all(x)) - x.begin()); //make all one after sorting
#define blt __builtin_popcount
/////////////////////print array, vector, deque, set, multiset, pair, map /////////////////////
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, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]"; cout << endl;}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]"; cout << endl;}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]"; cout << endl;}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]"; cout << endl;}
template <class T> void print(stack <T> v) {cerr << "[ "; stack<T> s = v; while(s.size()) {int i = s.top(); print(i); s.pop(); cerr << " ";} cerr << "]"; cout << endl;}
template <class T> void print(queue <T> v) {cerr << "[ "; queue<T> s = v; while(s.size()) {int i = s.front(); print(i); s.pop(); cerr << " ";} cerr << "]"; cout << endl;}
template <class T> void print(deque <T> v) {cerr << "[ "; deque<T> s = v; while(s.size()) {int i = s.front(); print(i); s.pop_front(); cerr << " ";} cerr << "]"; cout << endl;}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]"; cout << endl;}
template <class T, class V> void print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]"; cout << endl;}
/////////////////////code/////////////////////
vpi g[100005]; 
const int l = 18;
int m[100005], place[100005], id, up[100005][l + 1];
bool vis[100005];
vi ord;
set<pii> s;

void dfsmin(int v, int p) {
    m[v] = v;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i - 1]][i - 1];
    for(pii u : g[v]) {
        dfsmin(u.ss, v);
        m[v] = min(m[v], m[u.ss]);
    }
}

void dfsorder(int v) {
    for(pii& u : g[v]) u.ff = m[u.ss];
    sort(all(g[v]));
    for(pii u : g[v])
        dfsorder(u.ss);
    ord.pb(v);
    place[v] = id++;
}

int main() {
    fastio;
    int x, y, n, q, t, root; 
    cin >> n >> q;
    fri(n) {
        cin >> x;
        if(!x) root = i + 1;
        else g[x].eb(0, i + 1);
    }
    dfsmin(root, 0);
    dfsorder(root);
    for(int x : ord)
        s.insert({place[x], x});
    while(q--) {
        cin >> t >> x;
        if(t == 1) {
            pii p;
            fri(x) {
                p = *(s.begin());
                vis[p.ss] = 1;
                s.erase(s.begin());
            }
            cout << p.ss << '\n';
        }
        else {
            int u = x, cnt = 0;
            for(int i = l; i >= 0; --i) {
                if(vis[up[u][i]]) {
                    cnt += (1 << i);
                    u = up[u][i];
                }
            }
            cout << cnt << '\n';
            s.insert({place[u], u});
            vis[u] = 0;
        }
        // print(s); print(vis, n + 1);
    }
    return 0;
}

//	           ♥ ♥ ♥  ♥  ♥    ♥   ♥    ♥
//	           ♥      ♥  ♥     ♥ ♥    ♥ ♥
//	           ♥ ♥ ♥  ♥  ♥      ♥    ♥   ♥
//	           ♥      ♥  ♥      ♥   ♥ ♥ ♥ ♥
//	           ♥      ♥  ♥ ♥ ♥  ♥  ♥       ♥
//
//        God loves Fil, Fil accepts God's will

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:117:12: warning: unused variable 'y' [-Wunused-variable]
  117 |     int x, y, n, q, t, root;
      |            ^
ballmachine.cpp:125:13: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |     dfsorder(root);
      |     ~~~~~~~~^~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 101 ms 13832 KB Output is correct
3 Correct 60 ms 13684 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 3 ms 2808 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 6 ms 3332 KB Output is correct
10 Correct 18 ms 5332 KB Output is correct
11 Correct 98 ms 13828 KB Output is correct
12 Correct 61 ms 13796 KB Output is correct
13 Correct 81 ms 13780 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7624 KB Output is correct
2 Correct 142 ms 22772 KB Output is correct
3 Correct 81 ms 18712 KB Output is correct
4 Correct 51 ms 9308 KB Output is correct
5 Correct 53 ms 9100 KB Output is correct
6 Correct 52 ms 9160 KB Output is correct
7 Correct 50 ms 8284 KB Output is correct
8 Correct 34 ms 7608 KB Output is correct
9 Correct 149 ms 23244 KB Output is correct
10 Correct 134 ms 22792 KB Output is correct
11 Correct 124 ms 22808 KB Output is correct
12 Correct 135 ms 20772 KB Output is correct
13 Correct 104 ms 24200 KB Output is correct
14 Correct 84 ms 18592 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 12916 KB Output is correct
2 Correct 163 ms 21372 KB Output is correct
3 Correct 120 ms 22124 KB Output is correct
4 Correct 110 ms 18992 KB Output is correct
5 Correct 126 ms 18632 KB Output is correct
6 Correct 114 ms 18652 KB Output is correct
7 Correct 106 ms 17376 KB Output is correct
8 Correct 112 ms 22096 KB Output is correct
9 Correct 176 ms 23308 KB Output is correct
10 Correct 164 ms 22988 KB Output is correct
11 Correct 172 ms 23004 KB Output is correct
12 Correct 178 ms 21384 KB Output is correct
13 Correct 168 ms 27316 KB Output is correct
14 Correct 126 ms 19148 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 23524 KB Output is correct
2 Correct 154 ms 21352 KB Output is correct
3 Correct 149 ms 26908 KB Output is correct
4 Correct 177 ms 23500 KB Output is correct
5 Correct 145 ms 22912 KB Output is correct
6 Correct 174 ms 22940 KB Output is correct
7 Correct 160 ms 21304 KB Output is correct
8 Correct 116 ms 26880 KB Output is correct
9 Correct 90 ms 18660 KB Output is correct