oj.uz

Submission #283149

# Submission time Handle Problem Language Result Execution time Memory
283149 2020-08-25T10:37:27 Z AKaan37 Ball Machine (BOI13_ballmachine) C++17
17.6984 / 100
 1000 ms 18500 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]] || st.find(par[x][i])!=st.end())continue;
			x=par[x][i];
			cev+=(1<<i);
		}
		vis[par[x][0]]++;
		st.insert(x);
		printf("%d\n",cev);
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:78:7: warning: unused variable 'y' [-Wunused-variable]
   78 |   int y=x;
      |       ^
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 1095 ms 10744 KB Time limit exceeded
3 Incorrect 90 ms 11000 KB Output isn't correct
4 Execution timed out 1086 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 1 ms 512 KB Output isn't correct
8 Execution timed out 1093 ms 512 KB Time limit exceeded
9 Execution timed out 1090 ms 1024 KB Time limit exceeded
10 Execution timed out 1097 ms 3200 KB Time limit exceeded
11 Execution timed out 1084 ms 10616 KB Time limit exceeded
12 Incorrect 85 ms 11032 KB Output isn't correct
13 Incorrect 178 ms 10804 KB Output isn't correct

Subtask #2
8.57142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3448 KB Output is correct
2 Execution timed out 1052 ms 15096 KB Time limit exceeded
3 Correct 104 ms 16376 KB Output is correct
4 Execution timed out 1094 ms 5760 KB Time limit exceeded
5 Execution timed out 1084 ms 4864 KB Time limit exceeded
6 Execution timed out 1086 ms 5320 KB Time limit exceeded
7 Execution timed out 1092 ms 5368 KB Time limit exceeded
8 Correct 41 ms 3320 KB Output is correct
9 Execution timed out 1063 ms 15352 KB Time limit exceeded
10 Execution timed out 1095 ms 15012 KB Time limit exceeded
11 Incorrect 151 ms 15220 KB Output isn't correct
12 Incorrect 185 ms 15352 KB Output isn't correct
13 Incorrect 94 ms 12280 KB Output isn't correct
14 Correct 108 ms 16376 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 9592 KB Output isn't correct
2 Incorrect 309 ms 18296 KB Output isn't correct
3 Correct 276 ms 13984 KB Output is correct
4 Incorrect 149 ms 13176 KB Output isn't correct
5 Incorrect 148 ms 13432 KB Output isn't correct
6 Incorrect 164 ms 13408 KB Output isn't correct
7 Incorrect 183 ms 13560 KB Output isn't correct
8 Correct 250 ms 13944 KB Output is correct
9 Incorrect 334 ms 18360 KB Output isn't correct
10 Incorrect 368 ms 18424 KB Output isn't correct
11 Incorrect 325 ms 18356 KB Output isn't correct
12 Incorrect 327 ms 18296 KB Output isn't correct
13 Correct 427 ms 18500 KB Output is correct
14 Incorrect 223 ms 18128 KB Output isn't correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1049 ms 14456 KB Time limit exceeded
2 Incorrect 243 ms 16348 KB Output isn't correct
3 Incorrect 106 ms 13668 KB Output isn't correct
4 Execution timed out 1099 ms 14456 KB Time limit exceeded
5 Execution timed out 1081 ms 15100 KB Time limit exceeded
6 Execution timed out 1083 ms 15224 KB Time limit exceeded
7 Incorrect 268 ms 16348 KB Output isn't correct
8 Incorrect 109 ms 13732 KB Output isn't correct
9 Correct 131 ms 16376 KB Output is correct