oj.uz

Submission #535488

# Submission time Handle Problem Language Result Execution time Memory
535488 2022-03-10T11:24:21 Z faik Ball Machine (BOI13_ballmachine) C++14
7.53968 / 100
 1000 ms 37024 KB 
#include <bits/stdc++.h>

using namespace std;

#define MOD 998244353
#define INF 1000000001
#define LNF 1000000000000000001

#define int ll

typedef long long ll;
typedef pair<int,int> pii;

int dfsmin(int x,int last,vector<vector<int> > &edges,vector<int> &mn, vector<int> &height){
	int ret = x;
	if(last == x)
		height[x] = 0;
	else
		height[x] = height[last]+1;
	for(int i : edges[x]){
		if(i != last){
			ret = min(ret,dfsmin(i,x,edges,mn,height));
		}
	}
	sort(edges[x].begin(), edges[x].end(),[&mn](int a,int b){return mn[a] < mn[b];});
	mn[x] = ret;
	return ret;
}

void dfssec(int x,int last,vector<vector<int> > &edges, vector<int> &sec){
	static int counter = 0;
	for(int i : edges[x]){
		if(i != last){
			dfssec(i,x,edges,sec);
		}
	}
	sec[x] = counter++;
}
int l;

int lg(int x){
	int cnt = 0;
	while(x){x>>=1;cnt++;}
	return cnt;
}

void solve(){
//#define TEST
	int n,q;cin >> n >> q;
	vector<vector<int> > edges(n);
	vector<int> parent(n);
	for(int i = 0;i < n;i++){
		int p;cin >> p;p--;
		if(p != -1){
			edges[i].push_back(p);
			edges[p].push_back(i);
			parent[i] = p;
		}
	}

	vector<int> height(n);
	vector<int> mn(n);
	dfsmin(0,0,edges,mn,height);
	
	vector<int> sec(n);
	dfssec(0,0,edges,sec);
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	for(int i = 0;i < n;i++){
		pq.push({sec[i],i});
	}

	l = lg(n);
	vector<vector<int> > up(n);
	up.assign(n,vector<int>(l+1,0));
	for(int i = 0;i < n;i++)
		up[i][0] = parent[i];

	for(int i = 1;i <= l;i++){
		for(int j = 0;j < n;j++){
			up[j][i] = up[up[j][i-1]][i-1];
		}
	}
	vector<int> filled(n);
	for(int t = 0;t < q;t++){
		int i,x;cin >> i >> x;
		if(i == 1){
			int last;
			for(int j = 0;j < x;j++){
				last = pq.top().second;
				pq.pop();
				filled[last] = true;
			}
			cout << last+1 << '\n';
		} else if(i == 2){
			x--;
			int next = x;
			for(int j = l;j >= 0;j--){
				while(filled[up[next][j]] && next != 0){
					next = up[next][j];
				}
			}
			filled[next] = false;
			pq.push({sec[next],next});
			cout << height[x]-height[next] << '\n';
		}
	}
}

signed main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
#ifdef DEBUG
	freopen("i.txt","r",stdin);
	freopen("o.txt","w",stdout);
#endif
	int t = 1;
#ifdef TEST
	cin >> t;
#endif
	while(t--){
		solve();
	}

	return 0;
}

Compilation message

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:93:17: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |    cout << last+1 << '\n';
      |                 ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 121 ms 19248 KB Output isn't correct
3 Incorrect 89 ms 19452 KB Output isn't correct
4 Execution timed out 1080 ms 212 KB Time limit exceeded
5 Incorrect 1 ms 340 KB Output isn't correct
6 Incorrect 1 ms 468 KB Output isn't correct
7 Execution timed out 1083 ms 468 KB Time limit exceeded
8 Incorrect 1 ms 468 KB Output isn't correct
9 Incorrect 6 ms 1364 KB Output isn't correct
10 Incorrect 20 ms 4792 KB Output isn't correct
11 Incorrect 105 ms 19176 KB Output isn't correct
12 Incorrect 67 ms 19404 KB Output isn't correct
13 Incorrect 90 ms 19252 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7140 KB Output is correct
2 Execution timed out 1087 ms 32972 KB Time limit exceeded
3 Incorrect 114 ms 30080 KB Output isn't correct
4 Incorrect 59 ms 10196 KB Output isn't correct
5 Incorrect 71 ms 10080 KB Output isn't correct
6 Incorrect 59 ms 10432 KB Output isn't correct
7 Execution timed out 1091 ms 9036 KB Time limit exceeded
8 Correct 29 ms 7108 KB Output is correct
9 Incorrect 191 ms 34384 KB Output isn't correct
10 Execution timed out 1094 ms 32756 KB Time limit exceeded
11 Incorrect 245 ms 33628 KB Output isn't correct
12 Incorrect 188 ms 33080 KB Output isn't correct
13 Correct 113 ms 32456 KB Output is correct
14 Incorrect 112 ms 30052 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 15948 KB Time limit exceeded
2 Execution timed out 1084 ms 33024 KB Time limit exceeded
3 Execution timed out 1087 ms 28968 KB Time limit exceeded
4 Incorrect 145 ms 27696 KB Output isn't correct
5 Incorrect 148 ms 26756 KB Output isn't correct
6 Incorrect 123 ms 27564 KB Output isn't correct
7 Incorrect 144 ms 26328 KB Output isn't correct
8 Execution timed out 1081 ms 28956 KB Time limit exceeded
9 Execution timed out 1090 ms 34280 KB Time limit exceeded
10 Incorrect 223 ms 33072 KB Output isn't correct
11 Incorrect 254 ms 34148 KB Output isn't correct
12 Execution timed out 1096 ms 32828 KB Time limit exceeded
13 Execution timed out 1094 ms 37024 KB Time limit exceeded
14 Incorrect 155 ms 30012 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 230 ms 34776 KB Output isn't correct
2 Incorrect 193 ms 32572 KB Output isn't correct
3 Correct 140 ms 36416 KB Output is correct
4 Incorrect 202 ms 34760 KB Output isn't correct
5 Incorrect 268 ms 32884 KB Output isn't correct
6 Incorrect 188 ms 33860 KB Output isn't correct
7 Incorrect 200 ms 32584 KB Output isn't correct
8 Correct 160 ms 36552 KB Output is correct
9 Incorrect 102 ms 30176 KB Output isn't correct