oj.uz

답안 #73123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73123 2018-08-27T17:40:43 Z bharat2002 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 527 ms 42464 KB 
/*input
8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define f first
#define s second
inline pii mp(int a, int b)
{
	pii temp;temp.f=a;temp.s=b;return temp;
}
int n, q;vector<int> adjlist[100001];
int root;
int parent[100001][20], mval[100001];
void dfs(int i)
{
	mval[i]=i;
	for(auto j:adjlist[i])
	{
		dfs(j);mval[i]=min(mval[i], mval[j]);
	}
}
int cur, val[100001];bool done[100001];
void dfs2(int i)
{
	for(auto j:adjlist[i])
	{
		dfs2(j);
	}
	val[i]=cur++;
}
struct comp
{
	bool operator() (const int &a, const int &b)
	{
		return val[b]<val[a];
	}
};
priority_queue<int, vector<int>, comp > pq;
bool sf(int a, int b)
{
	return mval[a]<mval[b];
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		int f;cin>>f;
		if(f==0) {root=i;}
		else {adjlist[f].push_back(i);}
		parent[i][0]=f;
	}
	for(int j=1;j<20;j++)
	{
		for(int i=1;i<=n;i++)
		{
			parent[i][j]=parent[parent[i][j-1]][j-1];
		}
	}
	dfs(root);
	for(int i=1;i<=n;i++)
	{
		sort(adjlist[i].begin(), adjlist[i].end(), sf);
	}
	cur=1;dfs2(root);
	for(int i=1;i<=n;i++)
	{
		pq.push(i);
	}
	while(q--)
	{
		int t, k;cin>>t>>k;
		if(t==1)
		{
			int ans;
			while(k--)
			{
				ans=pq.top();done[ans]=1;pq.pop();
			}
			cout<<ans<<endl;
		}
		else
		{
			int ans=0;
			int j=19;
			while(j>=0)
			{
				if(done[parent[k][j]]) {k=parent[k][j];ans+=(1<<j);}
				j--;
			}
//			ans++;
			done[k]=0;cout<<ans<<endl;pq.push(k);
		}
	}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 355 ms 16800 KB Output is correct
3 Correct 283 ms 17344 KB Output is correct
4 Correct 5 ms 17344 KB Output is correct
5 Correct 5 ms 17344 KB Output is correct
6 Correct 6 ms 17344 KB Output is correct
7 Correct 10 ms 17344 KB Output is correct
8 Correct 7 ms 17344 KB Output is correct
9 Correct 23 ms 17344 KB Output is correct
10 Correct 63 ms 17344 KB Output is correct
11 Correct 407 ms 17904 KB Output is correct
12 Correct 284 ms 18280 KB Output is correct
13 Correct 364 ms 18752 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 18752 KB Output is correct
2 Correct 412 ms 28900 KB Output is correct
3 Correct 296 ms 28900 KB Output is correct
4 Correct 249 ms 28900 KB Output is correct
5 Correct 241 ms 28900 KB Output is correct
6 Correct 204 ms 28900 KB Output is correct
7 Correct 261 ms 28900 KB Output is correct
8 Correct 179 ms 28900 KB Output is correct
9 Correct 367 ms 31876 KB Output is correct
10 Correct 441 ms 31876 KB Output is correct
11 Correct 408 ms 32572 KB Output is correct
12 Correct 458 ms 32572 KB Output is correct
13 Correct 346 ms 33616 KB Output is correct
14 Correct 270 ms 33616 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 33616 KB Output is correct
2 Correct 481 ms 33616 KB Output is correct
3 Correct 339 ms 33616 KB Output is correct
4 Correct 313 ms 33616 KB Output is correct
5 Correct 288 ms 33616 KB Output is correct
6 Correct 263 ms 33616 KB Output is correct
7 Correct 270 ms 33616 KB Output is correct
8 Correct 304 ms 33616 KB Output is correct
9 Correct 398 ms 35360 KB Output is correct
10 Correct 395 ms 35360 KB Output is correct
11 Correct 466 ms 35360 KB Output is correct
12 Correct 466 ms 35360 KB Output is correct
13 Correct 527 ms 38764 KB Output is correct
14 Correct 345 ms 38764 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 424 ms 38764 KB Output is correct
2 Correct 427 ms 38764 KB Output is correct
3 Correct 389 ms 40076 KB Output is correct
4 Correct 423 ms 40076 KB Output is correct
5 Correct 411 ms 40076 KB Output is correct
6 Correct 330 ms 40076 KB Output is correct
7 Correct 396 ms 40076 KB Output is correct
8 Correct 367 ms 42464 KB Output is correct
9 Correct 254 ms 42464 KB Output is correct