oj.uz

Submission #963416

# Submission time Handle Problem Language Result Execution time Memory
963416 2024-04-15T01:24:02 Z pcc Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 127 ms 45328 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;
vector<int> tree[mxn];
vector<int> eul;
int par[mxn][20],dep[mxn];
int N,Q;
int rt;
int dp[mxn];
int dfn[mxn];
set<int> st;

void dfs(int now){
	for(int i = 1;i<20;i++)par[now][i] = par[par[now][i-1]][i-1];
	sort(tree[now].begin(),tree[now].end());
	for(auto nxt:tree[now]){
		dep[nxt] = dep[now]+1;
		par[nxt][0] = now;
		dfs(nxt);
	}
	dfn[now] = eul.size();
	eul.push_back(now);
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++){
		int p;
		cin>>p;
		par[i][0] = p;
		tree[p].push_back(i);
		if(!p)rt = i;
	}
	par[rt][0] = rt;
	dfs(rt);
	for(int i = 0;i<N;i++)st.insert(i);
	int C = 0;
	while(Q--){
		int t,k;
		cin>>t>>k;
		int lst = 0;
		assert(C == N-st.size());
		if(t == 1){
			C += k;
			while(k--){
				lst = *st.begin();
				st.erase(st.begin());
				dp[eul[lst]] = true;
			}
			cout<<eul[lst]<<'\n';
		}
		else{
			C--;
			lst = k;
			for(int i = 19;i>=0;i--){
				if(dp[par[lst][i]])lst = par[lst][i];
			}
			dp[lst] = false;
			st.insert(dfn[lst]);
			cout<<dep[k]-dep[lst]<<'\n';
		}
	}
	return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from ballmachine.cpp:1:
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:52:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   assert(C == N-st.size());
      |          ~~^~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 10844 KB Execution killed with signal 6
2 Runtime error 36 ms 28296 KB Execution killed with signal 6
3 Runtime error 34 ms 28116 KB Execution killed with signal 6
4 Runtime error 6 ms 10588 KB Execution killed with signal 6
5 Runtime error 7 ms 10844 KB Execution killed with signal 6
6 Runtime error 6 ms 10844 KB Execution killed with signal 6
7 Runtime error 6 ms 10840 KB Execution killed with signal 6
8 Runtime error 6 ms 10844 KB Execution killed with signal 6
9 Runtime error 7 ms 11356 KB Execution killed with signal 6
10 Runtime error 13 ms 17244 KB Execution killed with signal 6
11 Runtime error 39 ms 28236 KB Execution killed with signal 6
12 Runtime error 35 ms 28112 KB Execution killed with signal 6
13 Runtime error 36 ms 28184 KB Execution killed with signal 6

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 10588 KB Output is correct
2 Runtime error 79 ms 44036 KB Execution killed with signal 6
3 Runtime error 50 ms 36552 KB Execution killed with signal 6
4 Runtime error 20 ms 21592 KB Execution killed with signal 6
5 Runtime error 21 ms 21200 KB Execution killed with signal 6
6 Runtime error 21 ms 21180 KB Execution killed with signal 6
7 Runtime error 19 ms 20056 KB Execution killed with signal 6
8 Correct 26 ms 10468 KB Output is correct
9 Runtime error 78 ms 45260 KB Execution killed with signal 6
10 Runtime error 67 ms 44064 KB Execution killed with signal 6
11 Runtime error 64 ms 44100 KB Execution killed with signal 6
12 Runtime error 79 ms 40848 KB Execution killed with signal 6
13 Correct 71 ms 24784 KB Output is correct
14 Runtime error 50 ms 36528 KB Execution killed with signal 6

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 15072 KB Output isn't correct
2 Runtime error 70 ms 40892 KB Execution killed with signal 6
3 Correct 92 ms 23928 KB Output is correct
4 Runtime error 51 ms 40648 KB Execution killed with signal 6
5 Runtime error 56 ms 40124 KB Execution killed with signal 6
6 Runtime error 52 ms 40128 KB Execution killed with signal 6
7 Runtime error 49 ms 37376 KB Execution killed with signal 6
8 Correct 76 ms 23608 KB Output is correct
9 Runtime error 126 ms 45260 KB Execution killed with signal 6
10 Runtime error 100 ms 44500 KB Execution killed with signal 6
11 Runtime error 85 ms 44324 KB Execution killed with signal 6
12 Runtime error 62 ms 40912 KB Execution killed with signal 6
13 Correct 127 ms 26684 KB Output is correct
14 Runtime error 54 ms 36636 KB Execution killed with signal 6

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 45328 KB Execution killed with signal 6
2 Runtime error 60 ms 40908 KB Execution killed with signal 6
3 Correct 76 ms 26540 KB Output is correct
4 Runtime error 76 ms 45012 KB Execution killed with signal 6
5 Runtime error 76 ms 44164 KB Execution killed with signal 6
6 Runtime error 69 ms 44240 KB Execution killed with signal 6
7 Runtime error 63 ms 40904 KB Execution killed with signal 6
8 Correct 76 ms 26524 KB Output is correct
9 Runtime error 48 ms 36536 KB Execution killed with signal 6