oj.uz

Submission #777855

# Submission time Handle Problem Language Result Execution time Memory
777855 2023-07-09T19:06:14 Z raysh07 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 125 ms 32964 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n, q;
const int N = 1e5 + 69;
int lift[N][19], pr[N], root = -1;
bool occ[N];
int mn[N];
vector <int> adj[N];
int timer = 0;
int dep[N];

void dfs(int u){
	mn[u] = u;
	for (int v : adj[u]){
		dep[v] = dep[u] + 1;
		dfs(v);
		mn[u] = min(mn[u], mn[v]);
	}
}

bool comp(int a, int b){
	return mn[a] < mn[b];
}

void dfs2(int u){
	for (int v : adj[u]){
		dfs2(v);
	}

	pr[u] = ++timer;
}

void Solve()
{
	cin >> n >> q;

	for (int i = 1; i <= n; i++){
		int x; cin >> x;
		lift[i][0] = x;
		adj[x].push_back(i);
		if (x == 0) root = i;

		mn[i] = INF;
	}

	dfs(root);

	for (int i = 1; i <= n; i++){
		sort(adj[i].begin(), adj[i].end(), comp);
	}

	for (int j = 1; j <= 18; j++){
		for (int i = 1; i <= n; i++){
			lift[i][j] = lift[lift[i][j - 1]][j - 1];
		}
	}

	//todo : find list of priorities and push into multiset
	dfs2(root);
	
	priority_queue <pair<int, int>> pq;
	for (int i = 1; i <= n; i++){
		pq.push({-pr[i], i}); 
	}

	for (int i = 1; i <= q; i++){
		int t, x; cin >> t >> x;

		if (t == 1){
			//choose x highest priorities 
			for (int i = 1; i <= x; i++){
				auto pi = pq.top();
				pq.pop();

				int u = pi.s;
				occ[u] = true;

				if (i == x)
				cout << u << "\n";
			}
		} else {
			//find highest occupied parent of x
			assert(occ[x]);
			int y = x;
			for (int i = 18; i >= 0; i--){
				if (occ[lift[y][i]]){
					y = lift[y][i];
				}
			}

			occ[y] = false;
			cout << dep[x] - dep[y] << "\n";
			pq.push({-pr[y], y});
		}
	}
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 69 ms 17516 KB Output is correct
3 Correct 45 ms 17432 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 3 ms 2900 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 5 ms 3668 KB Output is correct
10 Correct 15 ms 6428 KB Output is correct
11 Correct 71 ms 17520 KB Output is correct
12 Correct 45 ms 17488 KB Output is correct
13 Correct 64 ms 17552 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8692 KB Output is correct
2 Correct 103 ms 28416 KB Output is correct
3 Correct 67 ms 24384 KB Output is correct
4 Correct 43 ms 11068 KB Output is correct
5 Correct 43 ms 10888 KB Output is correct
6 Correct 41 ms 10948 KB Output is correct
7 Correct 42 ms 9924 KB Output is correct
8 Correct 27 ms 8744 KB Output is correct
9 Correct 109 ms 28832 KB Output is correct
10 Correct 122 ms 28400 KB Output is correct
11 Correct 90 ms 28368 KB Output is correct
12 Correct 100 ms 26344 KB Output is correct
13 Correct 71 ms 29116 KB Output is correct
14 Correct 63 ms 24356 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15888 KB Output is correct
2 Correct 116 ms 27036 KB Output is correct
3 Correct 95 ms 26776 KB Output is correct
4 Correct 70 ms 23704 KB Output is correct
5 Correct 69 ms 23360 KB Output is correct
6 Correct 79 ms 23416 KB Output is correct
7 Correct 77 ms 22200 KB Output is correct
8 Correct 88 ms 26788 KB Output is correct
9 Correct 121 ms 28964 KB Output is correct
10 Correct 115 ms 28548 KB Output is correct
11 Correct 111 ms 28528 KB Output is correct
12 Correct 118 ms 26948 KB Output is correct
13 Correct 125 ms 32964 KB Output is correct
14 Correct 86 ms 24816 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 29100 KB Output is correct
2 Correct 121 ms 26944 KB Output is correct
3 Correct 89 ms 32444 KB Output is correct
4 Correct 120 ms 29156 KB Output is correct
5 Correct 110 ms 28516 KB Output is correct
6 Correct 94 ms 28480 KB Output is correct
7 Correct 107 ms 26916 KB Output is correct
8 Correct 74 ms 32540 KB Output is correct
9 Correct 62 ms 24416 KB Output is correct