oj.uz

Submission #283123

# Submission time Handle Problem Language Result Execution time Memory
283123 2020-08-25T10:13:11 Z AKaan37 Ball Machine (BOI13_ballmachine) C++17
0 / 100
 1000 ms 17020 KB 
//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,vis[li],root,par[li][LOG],last;
int cev;
set<int> st;
string s;
vector<int> v;

inline void build_lca(){
	for(int i=1;i<=27;i++){
		for(int j=1;j<=n;j++)par[j][i]=par[par[j][i-1]][i-1];
	}
}

int main(void){
	scanf("%d %d",&n,&t);
	FOR{
		int x;
		scanf("%d",&x);
		if(x==0){
			root=x;
		}
		else{
			vis[x]++;
			par[i][0]=x;
		}
	}
	FOR{
		if(vis[i]==0)st.insert(i);
	}
	build_lca();
	vis[0]=1000000;
	while(t--){
		int type;
		scanf("%d",&type);
		if(type==1){
			scanf("%d",&k);
			while(k){
				k--;
				auto it=st.begin();
				last=*it;
				//~ cout<<last<<endl;
				vis[par[*it][0]]--;
				if(vis[par[*it][0]]==0)st.insert(par[*it][0]);
				st.erase(it);
			}
			printf("%d\n",last);
			continue;
		}
		int x;
		scanf("%d",&x);
		int y=x;
		cev=0;
		for(int i=27;i>=0;i--){
			if(vis[par[x][i]])continue;
			x=par[x][i];
			cev+=(1<<i);
		}
		//~ vis[x]=1;
		if(st.find(x)!=st.end())st.erase(x);
		//~ st.insert(x);
		vis[x]++;
		for(int i=27;i>=0;i--){
			if(vis[par[y][i]] || par[y][i]==x)continue;
			y=par[y][i];
			//~ cev+=(1<<i);
		}
		st.insert(y);
		vis[y]=0;
		printf("%d\n",cev);
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |  scanf("%d %d",&n,&t);
      |  ~~~~~^~~~~~~~~~~~~~~
ballmachine.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~
ballmachine.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%d",&type);
      |   ~~~~~^~~~~~~~~~~~
ballmachine.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |    scanf("%d",&k);
      |    ~~~~~^~~~~~~~~
ballmachine.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Execution timed out 1087 ms 11048 KB Time limit exceeded
3 Incorrect 95 ms 11256 KB Output isn't correct
4 Execution timed out 1090 ms 384 KB Time limit exceeded
5 Incorrect 1 ms 384 KB Output isn't correct
6 Incorrect 1 ms 512 KB Output isn't correct
7 Incorrect 2 ms 488 KB Output isn't correct
8 Execution timed out 1092 ms 512 KB Time limit exceeded
9 Execution timed out 1094 ms 1024 KB Time limit exceeded
10 Execution timed out 1089 ms 3064 KB Time limit exceeded
11 Execution timed out 1064 ms 10808 KB Time limit exceeded
12 Incorrect 102 ms 11128 KB Output isn't correct
13 Incorrect 181 ms 11128 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 3320 KB Output isn't correct
2 Incorrect 217 ms 15740 KB Output isn't correct
3 Incorrect 134 ms 16636 KB Output isn't correct
4 Execution timed out 1088 ms 4988 KB Time limit exceeded
5 Execution timed out 1083 ms 4864 KB Time limit exceeded
6 Execution timed out 1039 ms 5112 KB Time limit exceeded
7 Execution timed out 1082 ms 5112 KB Time limit exceeded
8 Incorrect 51 ms 3320 KB Output isn't correct
9 Execution timed out 1094 ms 14840 KB Time limit exceeded
10 Incorrect 207 ms 15736 KB Output isn't correct
11 Incorrect 171 ms 15864 KB Output isn't correct
12 Incorrect 208 ms 15480 KB Output isn't correct
13 Incorrect 108 ms 12536 KB Output isn't correct
14 Incorrect 131 ms 16508 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 7800 KB Output isn't correct
2 Incorrect 233 ms 15992 KB Output isn't correct
3 Incorrect 128 ms 11256 KB Output isn't correct
4 Incorrect 142 ms 12024 KB Output isn't correct
5 Incorrect 138 ms 12536 KB Output isn't correct
6 Incorrect 140 ms 12536 KB Output isn't correct
7 Incorrect 145 ms 12608 KB Output isn't correct
8 Incorrect 124 ms 11256 KB Output isn't correct
9 Incorrect 249 ms 15464 KB Output isn't correct
10 Incorrect 243 ms 16120 KB Output isn't correct
11 Incorrect 249 ms 15992 KB Output isn't correct
12 Incorrect 247 ms 15992 KB Output isn't correct
13 Incorrect 212 ms 14456 KB Output isn't correct
14 Incorrect 228 ms 17020 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 15352 KB Time limit exceeded
2 Incorrect 228 ms 15864 KB Output isn't correct
3 Incorrect 110 ms 14072 KB Output isn't correct
4 Execution timed out 1093 ms 15352 KB Time limit exceeded
5 Incorrect 228 ms 15992 KB Output isn't correct
6 Incorrect 181 ms 15864 KB Output isn't correct
7 Incorrect 226 ms 15992 KB Output isn't correct
8 Incorrect 112 ms 14072 KB Output isn't correct
9 Incorrect 120 ms 16504 KB Output isn't correct