oj.uz

답안 #51525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51525 2018-06-18T07:08:50 Z WA_TLE Ball Machine (BOI13_ballmachine) C++14
46.7643 / 100
 298 ms 24720 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(bas);
			cout<<ans<<"\n";
		}
	}
}

Subtask #1
1.92307692308 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 89 ms 8928 KB Output isn't correct
3 Incorrect 60 ms 9140 KB Output isn't correct
4 Incorrect 2 ms 9140 KB Output isn't correct
5 Incorrect 2 ms 9140 KB Output isn't correct
6 Correct 4 ms 9140 KB Output is correct
7 Incorrect 3 ms 9140 KB Output isn't correct
8 Incorrect 3 ms 9140 KB Output isn't correct
9 Incorrect 9 ms 9140 KB Output isn't correct
10 Incorrect 27 ms 9140 KB Output isn't correct
11 Incorrect 92 ms 9140 KB Output isn't correct
12 Incorrect 61 ms 9256 KB Output isn't correct
13 Incorrect 88 ms 9256 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 9256 KB Output isn't correct
2 Incorrect 169 ms 18596 KB Output isn't correct
3 Correct 92 ms 18596 KB Output is correct
4 Incorrect 56 ms 18596 KB Output isn't correct
5 Incorrect 61 ms 18596 KB Output isn't correct
6 Incorrect 56 ms 18596 KB Output isn't correct
7 Incorrect 80 ms 18596 KB Output isn't correct
8 Incorrect 34 ms 18596 KB Output isn't correct
9 Incorrect 182 ms 19088 KB Output isn't correct
10 Incorrect 153 ms 19088 KB Output isn't correct
11 Incorrect 126 ms 19088 KB Output isn't correct
12 Incorrect 158 ms 19088 KB Output isn't correct
13 Incorrect 113 ms 21748 KB Output isn't correct
14 Correct 79 ms 21748 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 21748 KB Output is correct
2 Correct 142 ms 21748 KB Output is correct
3 Correct 120 ms 21748 KB Output is correct
4 Correct 98 ms 21748 KB Output is correct
5 Correct 100 ms 21748 KB Output is correct
6 Correct 103 ms 21748 KB Output is correct
7 Correct 115 ms 21748 KB Output is correct
8 Correct 168 ms 21748 KB Output is correct
9 Correct 216 ms 21748 KB Output is correct
10 Correct 209 ms 21748 KB Output is correct
11 Correct 179 ms 21748 KB Output is correct
12 Correct 198 ms 21748 KB Output is correct
13 Correct 298 ms 24720 KB Output is correct
14 Correct 125 ms 24720 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 218 ms 24720 KB Output isn't correct
2 Incorrect 216 ms 24720 KB Output isn't correct
3 Incorrect 186 ms 24720 KB Output isn't correct
4 Incorrect 172 ms 24720 KB Output isn't correct
5 Incorrect 248 ms 24720 KB Output isn't correct
6 Incorrect 151 ms 24720 KB Output isn't correct
7 Incorrect 210 ms 24720 KB Output isn't correct
8 Incorrect 132 ms 24720 KB Output isn't correct
9 Correct 83 ms 24720 KB Output is correct