oj.uz

Submission #283157

# Submission time Handle Problem Language Result Execution time Memory
283157 2020-08-25T10:41:38 Z AKaan37 Ball Machine (BOI13_ballmachine) C++17
20.9524 / 100
 1000 ms 15628 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<=17;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=17;i>=0;i--){
			if(vis[par[x][i]] || st.find(par[x][i])!=st.end())continue;
			x=par[x][i];
			cev+=(1<<i);
		}
		if(vis[par[x][0]]==0)st.erase(par[x][0]);
		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 Execution timed out 1091 ms 384 KB Time limit exceeded
2 Execution timed out 1097 ms 9976 KB Time limit exceeded
3 Incorrect 86 ms 10232 KB Output isn't correct
4 Execution timed out 1044 ms 384 KB Time limit exceeded
5 Execution timed out 1033 ms 384 KB Time limit exceeded
6 Incorrect 1 ms 512 KB Output isn't correct
7 Execution timed out 1088 ms 512 KB Time limit exceeded
8 Execution timed out 1096 ms 512 KB Time limit exceeded
9 Execution timed out 1094 ms 896 KB Time limit exceeded
10 Execution timed out 1090 ms 2688 KB Time limit exceeded
11 Execution timed out 1092 ms 9976 KB Time limit exceeded
12 Incorrect 76 ms 10232 KB Output isn't correct
13 Incorrect 118 ms 9976 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2808 KB Output is correct
2 Execution timed out 1091 ms 14200 KB Time limit exceeded
3 Correct 155 ms 15608 KB Output is correct
4 Execution timed out 1038 ms 4600 KB Time limit exceeded
5 Execution timed out 1053 ms 4480 KB Time limit exceeded
6 Execution timed out 1096 ms 4600 KB Time limit exceeded
7 Execution timed out 1095 ms 4224 KB Time limit exceeded
8 Correct 44 ms 2808 KB Output is correct
9 Execution timed out 1094 ms 14584 KB Time limit exceeded
10 Execution timed out 1091 ms 14328 KB Time limit exceeded
11 Incorrect 140 ms 14456 KB Output isn't correct
12 Incorrect 182 ms 14328 KB Output isn't correct
13 Correct 94 ms 11384 KB Output is correct
14 Correct 93 ms 15608 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 7160 KB Output isn't correct
2 Incorrect 234 ms 14588 KB Output isn't correct
3 Correct 128 ms 10616 KB Output is correct
4 Incorrect 136 ms 11384 KB Output isn't correct
5 Incorrect 149 ms 11640 KB Output isn't correct
6 Incorrect 130 ms 11620 KB Output isn't correct
7 Incorrect 132 ms 11640 KB Output isn't correct
8 Correct 109 ms 10360 KB Output is correct
9 Incorrect 278 ms 14004 KB Output isn't correct
10 Incorrect 268 ms 14712 KB Output isn't correct
11 Incorrect 245 ms 14660 KB Output isn't correct
12 Incorrect 237 ms 14584 KB Output isn't correct
13 Correct 186 ms 13048 KB Output is correct
14 Incorrect 191 ms 15608 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 13688 KB Time limit exceeded
2 Incorrect 204 ms 14536 KB Output isn't correct
3 Correct 100 ms 12920 KB Output is correct
4 Execution timed out 1090 ms 13688 KB Time limit exceeded
5 Execution timed out 1089 ms 14328 KB Time limit exceeded
6 Execution timed out 1099 ms 14328 KB Time limit exceeded
7 Incorrect 216 ms 14540 KB Output isn't correct
8 Correct 101 ms 12896 KB Output is correct
9 Correct 112 ms 15628 KB Output is correct