oj.uz

Submission #255613

# Submission time Handle Problem Language Result Execution time Memory
255613 2020-08-01T12:37:35 Z amoo_safar Ball Machine (BOI13_ballmachine) C++14
100 / 100
 287 ms 31992 KB 
// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 20;

int n, q, rt;
int par[N][Log];
int mn[N];

vector<int> G[N];

void DFS(int u, int p){
	par[u][0] = p;
	mn[u] = u;
	for(int i = 1; i < Log; i++) par[u][i] = par[par[u][i - 1]][i - 1];
	for(auto adj : G[u]){
		DFS(adj, u);
		mn[u] = min(mn[u], mn[adj]);
	}
}

set<int> st;

int mk[N], fn[N], rfn[N], T = 0;
void DFS2(int u){
	sort(all(G[u]), [&](int i, int j){
		return mn[i] < mn[j];
	});
	for(auto adj : G[u]){
		DFS2(adj);
	}
	fn[u] = T ++;
	rfn[fn[u]] = u;
	st.insert(fn[u]);
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	int p;
	for(int i = 1; i <= n; i++){
		cin >> p;
		if(p) G[p].pb(i);
		else rt = i;
	}
	DFS(rt, 0);
	DFS2(rt);

	int ty, v, k, res;
	for(int i = 1; i <= q; i++){
		cin >> ty;
		if(ty == 1){
			cin >> k;
			for(int it = 0; it < k; it++){
				v = rfn[*st.begin()];
				st.erase(st.begin());
				mk[v] = 1;
			}
			cout << v << '\n';
		} else {
			cin >> v;
			res = 0;
			for(int lg = Log - 1; lg >= 0; lg--){
				if(mk[par[v][lg]]) res |= 1 << lg, v = par[v][lg];
			}
			mk[v] = 0;
			st.insert(fn[v]);
			cout << res << '\n';
		}
	}
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 127 ms 16716 KB Output is correct
3 Correct 90 ms 16376 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 5 ms 5248 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 4 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 9 ms 5760 KB Output is correct
10 Correct 23 ms 7936 KB Output is correct
11 Correct 132 ms 16672 KB Output is correct
12 Correct 82 ms 16376 KB Output is correct
13 Correct 106 ms 16632 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 10488 KB Output is correct
2 Correct 201 ms 26524 KB Output is correct
3 Correct 101 ms 21236 KB Output is correct
4 Correct 90 ms 12280 KB Output is correct
5 Correct 69 ms 11896 KB Output is correct
6 Correct 64 ms 11896 KB Output is correct
7 Correct 66 ms 10872 KB Output is correct
8 Correct 44 ms 10344 KB Output is correct
9 Correct 166 ms 26964 KB Output is correct
10 Correct 212 ms 26488 KB Output is correct
11 Correct 177 ms 26616 KB Output is correct
12 Correct 176 ms 24184 KB Output is correct
13 Correct 148 ms 28380 KB Output is correct
14 Correct 98 ms 21236 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 16120 KB Output is correct
2 Correct 273 ms 24740 KB Output is correct
3 Correct 181 ms 26360 KB Output is correct
4 Correct 175 ms 22520 KB Output is correct
5 Correct 168 ms 22224 KB Output is correct
6 Correct 165 ms 22136 KB Output is correct
7 Correct 171 ms 20600 KB Output is correct
8 Correct 178 ms 26356 KB Output is correct
9 Correct 260 ms 27124 KB Output is correct
10 Correct 287 ms 26744 KB Output is correct
11 Correct 246 ms 26744 KB Output is correct
12 Correct 246 ms 24816 KB Output is correct
13 Correct 221 ms 31992 KB Output is correct
14 Correct 193 ms 22132 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 27344 KB Output is correct
2 Correct 227 ms 24824 KB Output is correct
3 Correct 177 ms 31224 KB Output is correct
4 Correct 243 ms 27256 KB Output is correct
5 Correct 238 ms 26744 KB Output is correct
6 Correct 208 ms 26684 KB Output is correct
7 Correct 245 ms 24824 KB Output is correct
8 Correct 188 ms 31352 KB Output is correct
9 Correct 116 ms 21364 KB Output is correct