oj.uz

Submission #51526

# Submission time Handle Problem Language Result Execution time Memory
51526 2018-06-18T07:10:08 Z WA_TLE Ball Machine (BOI13_ballmachine) C++14
100 / 100
 243 ms 24728 KB 
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
//オイラーツアー
//addは自明
//eraseは留年二分探索
vector<int>oya;
vector<vector<int>>ko;
vector<int>tour;
vector<int>sai;
int ddfs(int ter){
	sai[ter]=ter;
	for(auto it:ko[ter]){mineq(sai[ter],ddfs(it));}
	return sai[ter];
}
void dfs(int ter){
	vector<pair<int,int>>aaa;
	for(auto it:ko[ter]){aaa.pub(mp(sai[it],it));}
	SO(aaa);
	for(auto it:aaa){dfs(it.sec);}
	tour.pub(ter);
}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int i,n,q;cin>>n>>q;
	//まずはオイラーツアーを構築する
	oya.res(n);
	ko.res(n);
	int rot=-1;
	for(i=0;i<n;i++){
		int a;cin>>a;a--;
		if(a<0){rot=i;}
		else{
			oya[i]=a;
			ko[a].pub(i);
		}
	}
	sai.res(n);
	ddfs(rot);
	tour.reserve(n);
	dfs(rot);
	vector<int>yusen(n);
	for(i=0;i<n;i++){yusen[tour[i]]=i;}
	priority_queue<int,vector<int>,greater<int>> que;
	vector<bool>aru(n+1);//aru[n]は常に空
	oya[rot]=n;
	for(i=0;i<n;i++){que.push(i);}
	array<vector<int>,17>dab;
	dab[0]=oya;
	dab[0].pub(n);
	for(int h=1;h<17;h++){
		dab[h].res(n+1);
		for(i=0;i<=n;i++){dab[h][i]=dab[h-1][dab[h-1][i]];}
	}
	while(q--){
		int type;cin>>type;
		if(type==1){
			int k;cin>>k;
			while(k--){
				//入る場所を求める
				int bas=tour[que.top()];
				que.pop();
				aru[bas]=1;
				if(k==0){cout<<bas+1<<"\n";}
			}
		}else{
			int x;cin>>x;
			//ない場所　を二分探索で求める
			int ans=0,bas=x-1;
			for(int h=16;h>=0;h--){
				if(aru[dab[h][bas]]){
					ans+=(1<<h);
					bas=dab[h][bas];
				}
			}
			aru[bas]=0;
			que.push(yusen[bas]);
			cout<<ans<<"\n";
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 102 ms 8872 KB Output is correct
3 Correct 76 ms 8972 KB Output is correct
4 Correct 2 ms 8972 KB Output is correct
5 Correct 2 ms 8972 KB Output is correct
6 Correct 3 ms 8972 KB Output is correct
7 Correct 3 ms 8972 KB Output is correct
8 Correct 3 ms 8972 KB Output is correct
9 Correct 7 ms 8972 KB Output is correct
10 Correct 19 ms 8972 KB Output is correct
11 Correct 89 ms 9084 KB Output is correct
12 Correct 69 ms 9232 KB Output is correct
13 Correct 91 ms 9232 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9232 KB Output is correct
2 Correct 165 ms 18480 KB Output is correct
3 Correct 77 ms 18480 KB Output is correct
4 Correct 56 ms 18480 KB Output is correct
5 Correct 70 ms 18480 KB Output is correct
6 Correct 56 ms 18480 KB Output is correct
7 Correct 56 ms 18480 KB Output is correct
8 Correct 36 ms 18480 KB Output is correct
9 Correct 143 ms 18936 KB Output is correct
10 Correct 194 ms 18936 KB Output is correct
11 Correct 165 ms 18936 KB Output is correct
12 Correct 142 ms 18936 KB Output is correct
13 Correct 114 ms 21864 KB Output is correct
14 Correct 79 ms 21864 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 21864 KB Output is correct
2 Correct 189 ms 21864 KB Output is correct
3 Correct 148 ms 21864 KB Output is correct
4 Correct 104 ms 21864 KB Output is correct
5 Correct 153 ms 21864 KB Output is correct
6 Correct 114 ms 21864 KB Output is correct
7 Correct 95 ms 21864 KB Output is correct
8 Correct 193 ms 21864 KB Output is correct
9 Correct 243 ms 21864 KB Output is correct
10 Correct 179 ms 21864 KB Output is correct
11 Correct 179 ms 21864 KB Output is correct
12 Correct 154 ms 21864 KB Output is correct
13 Correct 217 ms 24728 KB Output is correct
14 Correct 112 ms 24728 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 24728 KB Output is correct
2 Correct 185 ms 24728 KB Output is correct
3 Correct 151 ms 24728 KB Output is correct
4 Correct 225 ms 24728 KB Output is correct
5 Correct 181 ms 24728 KB Output is correct
6 Correct 150 ms 24728 KB Output is correct
7 Correct 154 ms 24728 KB Output is correct
8 Correct 155 ms 24728 KB Output is correct
9 Correct 88 ms 24728 KB Output is correct