oj.uz

Submission #283151

# Submission time Handle Problem Language Result Execution time Memory
283151 2020-08-25T10:39:21 Z AKaan37 Ball Machine (BOI13_ballmachine) C++17
17.6984 / 100
 1000 ms 17784 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);
		}
		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 1042 ms 9944 KB Time limit exceeded
3 Incorrect 74 ms 10360 KB Output isn't correct
4 Execution timed out 1063 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 1094 ms 512 KB Time limit exceeded
9 Execution timed out 1090 ms 896 KB Time limit exceeded
10 Execution timed out 1083 ms 2944 KB Time limit exceeded
11 Execution timed out 1094 ms 9856 KB Time limit exceeded
12 Incorrect 82 ms 10232 KB Output isn't correct
13 Incorrect 110 ms 10048 KB Output isn't correct

Subtask #2
8.57142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2868 KB Output is correct
2 Execution timed out 1075 ms 14264 KB Time limit exceeded
3 Correct 93 ms 15480 KB Output is correct
4 Execution timed out 1069 ms 5112 KB Time limit exceeded
5 Execution timed out 1087 ms 4480 KB Time limit exceeded
6 Execution timed out 1093 ms 4600 KB Time limit exceeded
7 Execution timed out 1093 ms 4732 KB Time limit exceeded
8 Correct 37 ms 2808 KB Output is correct
9 Execution timed out 1088 ms 14584 KB Time limit exceeded
10 Execution timed out 1092 ms 14204 KB Time limit exceeded
11 Incorrect 158 ms 14376 KB Output isn't correct
12 Incorrect 184 ms 14460 KB Output isn't correct
13 Incorrect 89 ms 11384 KB Output isn't correct
14 Correct 101 ms 15608 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 8980 KB Output isn't correct
2 Incorrect 276 ms 17528 KB Output isn't correct
3 Correct 226 ms 13176 KB Output is correct
4 Incorrect 147 ms 12280 KB Output isn't correct
5 Incorrect 136 ms 12664 KB Output isn't correct
6 Incorrect 135 ms 12664 KB Output isn't correct
7 Incorrect 136 ms 12792 KB Output isn't correct
8 Correct 222 ms 13176 KB Output is correct
9 Incorrect 324 ms 17532 KB Output isn't correct
10 Incorrect 287 ms 17528 KB Output isn't correct
11 Incorrect 284 ms 17528 KB Output isn't correct
12 Incorrect 302 ms 17528 KB Output isn't correct
13 Correct 398 ms 17784 KB Output is correct
14 Incorrect 188 ms 17372 KB Output isn't correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 13696 KB Time limit exceeded
2 Incorrect 220 ms 15608 KB Output isn't correct
3 Incorrect 92 ms 12848 KB Output isn't correct
4 Execution timed out 1054 ms 13696 KB Time limit exceeded
5 Execution timed out 1093 ms 14328 KB Time limit exceeded
6 Execution timed out 1093 ms 14420 KB Time limit exceeded
7 Incorrect 225 ms 15736 KB Output isn't correct
8 Incorrect 91 ms 12920 KB Output isn't correct
9 Correct 96 ms 15608 KB Output is correct