oj.uz

답안 #283241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283241 2020-08-25T11:59:45 Z AKaan37 Ball Machine (BOI13_ballmachine) C++17
20.9524 / 100
 1000 ms 29560 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,mini[li];
int cev;
multiset<PII> 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,i});
		mini[i]=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();
				PII p=*it;
				last=p.se;
				//~ cout<<p.fi<<endl;
				//~ if(last==212)cout<<k<<"**\n";
				//~ cout<<last<<endl;
				vis[par[p.se][0]]--;
				mini[par[p.se][0]]=min(mini[par[p.se][0]],p.fi);
				if(vis[par[p.se][0]]==0){st.insert({min(mini[par[p.se][0]],p.fi),par[p.se][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({mini[par[x][i]],par[x][i]})!=st.end())continue;
			x=par[x][i];
			cev+=(1<<i);
		}
		if(st.find({mini[par[x][0]],par[x][0]})!=st.end()){st.erase(st.find({mini[par[x][0]],par[x][0]}));}
		vis[par[x][0]]++;
		st.insert({mini[x],x});
		printf("%lld\n",cev);
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int32_t main()':
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:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |   scanf("%lld",&type);
      |   ~~~~~^~~~~~~~~~~~~~
ballmachine.cpp:70:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |    scanf("%lld",&k);
      |    ~~~~~^~~~~~~~~~~
ballmachine.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |   scanf("%lld",&x);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Execution timed out 1090 ms 19064 KB Time limit exceeded
3 Incorrect 85 ms 19320 KB Output isn't correct
4 Execution timed out 1059 ms 384 KB Time limit exceeded
5 Incorrect 1 ms 384 KB Output isn't correct
6 Incorrect 2 ms 640 KB Output isn't correct
7 Execution timed out 1093 ms 640 KB Time limit exceeded
8 Incorrect 2 ms 640 KB Output isn't correct
9 Execution timed out 1097 ms 1536 KB Time limit exceeded
10 Execution timed out 1091 ms 4992 KB Time limit exceeded
11 Incorrect 191 ms 19064 KB Output isn't correct
12 Incorrect 87 ms 19320 KB Output isn't correct
13 Incorrect 144 ms 19064 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 5240 KB Output is correct
2 Execution timed out 1091 ms 27760 KB Time limit exceeded
3 Correct 104 ms 29560 KB Output is correct
4 Execution timed out 1091 ms 8440 KB Time limit exceeded
5 Execution timed out 1090 ms 8576 KB Time limit exceeded
6 Execution timed out 1091 ms 8576 KB Time limit exceeded
7 Execution timed out 1098 ms 7936 KB Time limit exceeded
8 Correct 44 ms 5240 KB Output is correct
9 Execution timed out 1099 ms 27000 KB Time limit exceeded
10 Execution timed out 1079 ms 27896 KB Time limit exceeded
11 Execution timed out 1090 ms 27768 KB Time limit exceeded
12 Execution timed out 1094 ms 27416 KB Time limit exceeded
13 Correct 97 ms 22904 KB Output is correct
14 Correct 103 ms 29432 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 102 ms 13816 KB Output isn't correct
2 Incorrect 230 ms 28128 KB Output isn't correct
3 Correct 127 ms 20728 KB Output is correct
4 Incorrect 151 ms 22008 KB Output isn't correct
5 Incorrect 158 ms 22440 KB Output isn't correct
6 Incorrect 160 ms 22392 KB Output isn't correct
7 Incorrect 162 ms 22524 KB Output isn't correct
8 Correct 126 ms 20728 KB Output is correct
9 Incorrect 244 ms 27384 KB Output isn't correct
10 Incorrect 237 ms 28240 KB Output isn't correct
11 Incorrect 233 ms 28164 KB Output isn't correct
12 Incorrect 235 ms 28168 KB Output isn't correct
13 Correct 201 ms 25944 KB Output is correct
14 Incorrect 235 ms 29560 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 27000 KB Time limit exceeded
2 Incorrect 249 ms 28024 KB Output isn't correct
3 Correct 105 ms 25980 KB Output is correct
4 Execution timed out 1093 ms 27000 KB Time limit exceeded
5 Execution timed out 1093 ms 27896 KB Time limit exceeded
6 Incorrect 177 ms 27896 KB Output isn't correct
7 Incorrect 247 ms 28152 KB Output isn't correct
8 Correct 103 ms 25848 KB Output is correct
9 Correct 118 ms 29560 KB Output is correct