oj.uz

Submission #283131

# Submission time Handle Problem Language Result Execution time Memory
283131 2020-08-25T10:22:19 Z AKaan37 Ball Machine (BOI13_ballmachine) C++17
4.28571 / 100
 1000 ms 15736 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);
		else vis[par[x][0]]++;
		//~ 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 Execution timed out 1084 ms 384 KB Time limit exceeded
2 Execution timed out 1095 ms 9976 KB Time limit exceeded
3 Incorrect 89 ms 10232 KB Output isn't correct
4 Execution timed out 1098 ms 384 KB Time limit exceeded
5 Execution timed out 1099 ms 384 KB Time limit exceeded
6 Incorrect 1 ms 512 KB Output isn't correct
7 Incorrect 2 ms 512 KB Output isn't correct
8 Execution timed out 1092 ms 512 KB Time limit exceeded
9 Execution timed out 1044 ms 1024 KB Time limit exceeded
10 Execution timed out 1100 ms 2688 KB Time limit exceeded
11 Execution timed out 1089 ms 9848 KB Time limit exceeded
12 Incorrect 94 ms 10236 KB Output isn't correct
13 Incorrect 155 ms 9976 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 2808 KB Output isn't correct
2 Execution timed out 1095 ms 14260 KB Time limit exceeded
3 Correct 114 ms 15516 KB Output is correct
4 Execution timed out 1058 ms 4352 KB Time limit exceeded
5 Execution timed out 1099 ms 4480 KB Time limit exceeded
6 Execution timed out 1097 ms 4480 KB Time limit exceeded
7 Execution timed out 1093 ms 4224 KB Time limit exceeded
8 Incorrect 48 ms 2808 KB Output isn't correct
9 Execution timed out 1089 ms 13688 KB Time limit exceeded
10 Execution timed out 1089 ms 14200 KB Time limit exceeded
11 Execution timed out 1090 ms 14328 KB Time limit exceeded
12 Incorrect 219 ms 14204 KB Output isn't correct
13 Incorrect 115 ms 11500 KB Output isn't correct
14 Correct 115 ms 15576 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 7192 KB Output isn't correct
2 Incorrect 267 ms 14584 KB Output isn't correct
3 Incorrect 153 ms 10332 KB Output isn't correct
4 Incorrect 146 ms 11116 KB Output isn't correct
5 Incorrect 180 ms 11768 KB Output isn't correct
6 Incorrect 145 ms 11640 KB Output isn't correct
7 Incorrect 141 ms 11672 KB Output isn't correct
8 Incorrect 136 ms 10364 KB Output isn't correct
9 Incorrect 288 ms 14084 KB Output isn't correct
10 Incorrect 250 ms 14584 KB Output isn't correct
11 Incorrect 246 ms 14628 KB Output isn't correct
12 Incorrect 235 ms 14584 KB Output isn't correct
13 Incorrect 254 ms 13048 KB Output isn't correct
14 Incorrect 224 ms 15708 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 13692 KB Time limit exceeded
2 Incorrect 215 ms 14456 KB Output isn't correct
3 Incorrect 113 ms 12896 KB Output isn't correct
4 Execution timed out 1089 ms 13688 KB Time limit exceeded
5 Execution timed out 1077 ms 14328 KB Time limit exceeded
6 Execution timed out 1082 ms 14456 KB Time limit exceeded
7 Incorrect 222 ms 14584 KB Output isn't correct
8 Incorrect 123 ms 12920 KB Output isn't correct
9 Incorrect 128 ms 15736 KB Output isn't correct