oj.uz

Submission #944058

# Submission time Handle Problem Language Result Execution time Memory
944058 2024-03-12T07:52:05 Z tamir1 Ball Machine (BOI13_ballmachine) C++17
59.9206 / 100
 1000 ms 16984 KB 
#include<bits/stdc++.h>
#define ll int
#define ff first
#define ss second
using namespace std;
ll n,q,i,p[100005],sz[100005],root,x,y,u[100005],a[100005];
bitset<100005> vis;
vector<pair<ll,ll>> v[100005];
vector<ll> w[100005],t[100005];
pair<ll,ll> loc[100005];
void dfs(ll x){
	for(ll i:t[x]){
		dfs(i);
		a[x]=min(a[i],a[x]);
	}
}
ll update(ll x){
	ll idx=0;
	for(pair<ll,ll> i:v[x]){
		if(sz[i.ss]<w[i.ss].size()){
			idx=i.ss;
			break;
		}
	}
	if(idx!=0) return update(idx);
	else{
		sz[x]++;
		return w[x][sz[x]-1];
	}
}
ll roll(ll x){
	ll y=loc[x].ff,z=loc[x].ss;
	if(sz[y]<w[y].size() || sz[p[y]]==0){
		sz[y]--;
		return sz[y]-z+2;
	}
	return sz[y]-z+1+roll(p[y]);
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q;
	for(i=1;i<=n;i++){
		loc[i]={i,1};
		w[i].push_back(i);
		cin >> p[i];
		a[i]=i;
		u[p[i]]++;
	}
	for(i=1;i<=n;i++){
		if(u[i]==0){
			x=i;
			while(p[x]!=0){
				y=p[x];
				if(vis[x]==1) break;
				vis[x]=1;
				if(u[y]==1){
					p[x]=p[y];
					p[y]=-1;
					w[x].push_back(y);
					loc[y]={x,w[x].size()};
					a[x]=min(a[x],a[y]);
					vis[x]=0;
				}
				else x=y;
			}
		}
	}
	for(i=1;i<=n;i++){
		if(p[i]==-1) continue;
		if(p[i]==0) root=i;
		else t[p[i]].push_back(i);
	}
	dfs(root);
	for(i=1;i<=n;i++){
		if(p[i]!=-1 && p[i]!=0){
			v[p[i]].push_back({a[i],i});
		}
	}
	for(i=1;i<=n;i++){
		sort(v[i].begin(),v[i].end());
	}
	while(q--){
		cin >> x >> y;
		if(x==1){
			for(i=1;i<=y;i++)
				x=update(root);
			cout << x << "\n";
		}
		else{
			cout << roll(y)-1 << "\n";
		}
	}
}

Compilation message

ballmachine.cpp: In function 'int update(int)':
ballmachine.cpp:20:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   if(sz[i.ss]<w[i.ss].size()){
      |      ~~~~~~~~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int roll(int)':
ballmachine.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  if(sz[y]<w[y].size() || sz[p[y]]==0){
      |     ~~~~~^~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 76 ms 14516 KB Output is correct
3 Correct 38 ms 14292 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 6 ms 9084 KB Output is correct
10 Correct 12 ms 10164 KB Output is correct
11 Correct 66 ms 14488 KB Output is correct
12 Correct 36 ms 14384 KB Output is correct
13 Correct 53 ms 14304 KB Output is correct

Subtask #2
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10328 KB Output is correct
2 Execution timed out 1026 ms 16836 KB Time limit exceeded
3 Correct 43 ms 14796 KB Output is correct
4 Correct 25 ms 11100 KB Output is correct
5 Execution timed out 1076 ms 11100 KB Time limit exceeded
6 Execution timed out 1030 ms 11308 KB Time limit exceeded
7 Execution timed out 1068 ms 11092 KB Time limit exceeded
8 Correct 16 ms 10316 KB Output is correct
9 Correct 49 ms 15660 KB Output is correct
10 Execution timed out 1055 ms 16752 KB Time limit exceeded
11 Execution timed out 1030 ms 16592 KB Time limit exceeded
12 Execution timed out 1056 ms 15808 KB Time limit exceeded
13 Correct 30 ms 13772 KB Output is correct
14 Correct 37 ms 14676 KB Output is correct

Subtask #3
17.1428571429 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12124 KB Output is correct
2 Execution timed out 1081 ms 16048 KB Time limit exceeded
3 Correct 22 ms 13276 KB Output is correct
4 Correct 32 ms 14196 KB Output is correct
5 Execution timed out 1048 ms 15196 KB Time limit exceeded
6 Execution timed out 1036 ms 15036 KB Time limit exceeded
7 Execution timed out 1028 ms 14748 KB Time limit exceeded
8 Correct 23 ms 13276 KB Output is correct
9 Correct 48 ms 15568 KB Output is correct
10 Execution timed out 1072 ms 16848 KB Time limit exceeded
11 Execution timed out 1091 ms 16476 KB Time limit exceeded
12 Execution timed out 1022 ms 15952 KB Time limit exceeded
13 Correct 32 ms 14796 KB Output is correct
14 Execution timed out 1056 ms 14548 KB Time limit exceeded

Subtask #4
2.77777777778 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15820 KB Output is correct
2 Execution timed out 1057 ms 15888 KB Time limit exceeded
3 Correct 31 ms 14284 KB Output is correct
4 Correct 45 ms 15820 KB Output is correct
5 Execution timed out 1006 ms 16804 KB Time limit exceeded
6 Execution timed out 1041 ms 16984 KB Time limit exceeded
7 Execution timed out 1032 ms 16056 KB Time limit exceeded
8 Correct 31 ms 14416 KB Output is correct
9 Correct 36 ms 14792 KB Output is correct