oj.uz

Submission #283217

# Submission time Handle Problem Language Result Execution time Memory
283217 2020-08-25T11:28:43 Z AKaan37 Ball Machine (BOI13_ballmachine) C++17
20.9524 / 100
 1000 ms 29048 KB 
//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

#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 int long long
#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];
	}
}

int32_t main(void){
	scanf("%lld %lld",&n,&t);
	FOR{
		int x;
		scanf("%lld",&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("%lld",&type);
		if(type==1){
			scanf("%lld",&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("%lld\n",last);
			continue;
		}
		int x;
		scanf("%lld",&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(st.find(par[x][0])!=st.end())st.erase(par[x][0]);
		vis[par[x][0]]++;
		st.insert(x);
		printf("%lld\n",cev);
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:84:7: warning: unused variable 'y' [-Wunused-variable]
   84 |   int y=x;
      |       ^
ballmachine.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  scanf("%lld %lld",&n,&t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
ballmachine.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%lld",&x);
      |   ~~~~~^~~~~~~~~~~
ballmachine.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   scanf("%lld",&type);
      |   ~~~~~^~~~~~~~~~~~~~
ballmachine.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |    scanf("%lld",&k);
      |    ~~~~~^~~~~~~~~~~
ballmachine.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |   scanf("%lld",&x);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 384 KB Time limit exceeded
2 Execution timed out 1083 ms 19068 KB Time limit exceeded
3 Incorrect 80 ms 19192 KB Output isn't correct
4 Execution timed out 1087 ms 384 KB Time limit exceeded
5 Execution timed out 1094 ms 384 KB Time limit exceeded
6 Incorrect 1 ms 640 KB Output isn't correct
7 Execution timed out 1085 ms 640 KB Time limit exceeded
8 Execution timed out 1054 ms 640 KB Time limit exceeded
9 Execution timed out 1099 ms 1536 KB Time limit exceeded
10 Execution timed out 1087 ms 4992 KB Time limit exceeded
11 Execution timed out 1094 ms 18680 KB Time limit exceeded
12 Incorrect 81 ms 19192 KB Output isn't correct
13 Incorrect 156 ms 19064 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5528 KB Output is correct
2 Execution timed out 1087 ms 27384 KB Time limit exceeded
3 Correct 100 ms 28664 KB Output is correct
4 Execution timed out 1084 ms 9080 KB Time limit exceeded
5 Execution timed out 1092 ms 8448 KB Time limit exceeded
6 Execution timed out 1087 ms 8576 KB Time limit exceeded
7 Execution timed out 1098 ms 8056 KB Time limit exceeded
8 Correct 43 ms 5624 KB Output is correct
9 Execution timed out 1072 ms 26988 KB Time limit exceeded
10 Execution timed out 1087 ms 27256 KB Time limit exceeded
11 Execution timed out 1095 ms 27640 KB Time limit exceeded
12 Execution timed out 1077 ms 27128 KB Time limit exceeded
13 Correct 92 ms 23288 KB Output is correct
14 Correct 104 ms 28664 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 13944 KB Output isn't correct
2 Incorrect 261 ms 28152 KB Output isn't correct
3 Correct 130 ms 20984 KB Output is correct
4 Incorrect 159 ms 21880 KB Output isn't correct
5 Incorrect 155 ms 22264 KB Output isn't correct
6 Incorrect 151 ms 22264 KB Output isn't correct
7 Incorrect 154 ms 22264 KB Output isn't correct
8 Correct 121 ms 21028 KB Output is correct
9 Incorrect 288 ms 27512 KB Output isn't correct
10 Incorrect 263 ms 28116 KB Output isn't correct
11 Incorrect 257 ms 28024 KB Output isn't correct
12 Incorrect 262 ms 28196 KB Output isn't correct
13 Correct 203 ms 26488 KB Output is correct
14 Incorrect 213 ms 29048 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 26620 KB Time limit exceeded
2 Incorrect 232 ms 28152 KB Output isn't correct
3 Correct 101 ms 26232 KB Output is correct
4 Execution timed out 1088 ms 26616 KB Time limit exceeded
5 Execution timed out 1078 ms 27768 KB Time limit exceeded
6 Execution timed out 1087 ms 27896 KB Time limit exceeded
7 Incorrect 240 ms 28024 KB Output isn't correct
8 Correct 117 ms 26164 KB Output is correct
9 Correct 119 ms 28712 KB Output is correct