oj.uz

답안 #48430

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48430 2018-05-13T10:00:12 Z Pajaraja Ball Machine (BOI13_ballmachine) C++17
0 / 100
 195 ms 23868 KB 
#include<bits/stdc++.h>
using namespace std;
int pr[100007],p[20][100007],dd[100007],cnt;
bool bl[100007];
vector<int> g[100007];
struct comp {bool operator() (const int& a,const int& b) {return pr[a]>pr[b];}};
priority_queue<int,vector<int>,comp> pq;
void dfscalc(int s)
{
	dd[s]=s;
	for(int i=0;i<g[s].size();i++) dfscalc(g[s][i]);
	for(int i=0;i<g[s].size();i++) dd[s]=min(dd[s],dd[g[s][i]]);
}
int dfs(int s)
{
	priority_queue<pair<int,int> > ord;
	for(int i=0;i<g[s].size();i++) ord.push(make_pair(-dd[g[s][i]],g[s][i]));
	while(!ord.empty())
	{
		dfs(ord.top().second);
		ord.pop();
	}
	pr[s]=cnt++; 
}
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		g[t].push_back(i);
		p[0][i]=t;
	}
	for(int i=1;i<20;i++) for(int j=1;j<=n;j++) p[i][j]=p[i-1][p[i-1][j]];
	dfscalc(1);
	dfs(1);
	for(int i=1;i<=n;i++) pq.push(i);
	while(q--)
	{
		int t,a,tmp=0;
		scanf("%d%d",&t,&a);
		if(t==1)
		{
			while(a--)
			{
				tmp=pq.top();
				bl[tmp]=true;
				pq.pop();
			}
		}
		else
		{
			for(int i=19;i>=0;i--) if(bl[p[i][a]])
			{
				a=p[i][a];
				tmp+=(1<<i);
			}
			bl[a]=false;
			pq.push(a);
		}
		printf("%d\n",tmp);
	}
}

Compilation message

ballmachine.cpp: In function 'void dfscalc(int)':
ballmachine.cpp:11:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) dfscalc(g[s][i]);
              ~^~~~~~~~~~~~
ballmachine.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) dd[s]=min(dd[s],dd[g[s][i]]);
              ~^~~~~~~~~~~~
ballmachine.cpp: In function 'int dfs(int)':
ballmachine.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) ord.push(make_pair(-dd[g[s][i]],g[s][i]));
              ~^~~~~~~~~~~~
ballmachine.cpp:24:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~
ballmachine.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~
ballmachine.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&t,&a);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Incorrect 103 ms 9572 KB Output isn't correct
3 Incorrect 64 ms 9780 KB Output isn't correct
4 Incorrect 4 ms 9780 KB Output isn't correct
5 Incorrect 4 ms 9780 KB Output isn't correct
6 Incorrect 4 ms 9780 KB Output isn't correct
7 Incorrect 4 ms 9780 KB Output isn't correct
8 Incorrect 6 ms 9780 KB Output isn't correct
9 Incorrect 8 ms 9780 KB Output isn't correct
10 Incorrect 20 ms 9780 KB Output isn't correct
11 Incorrect 93 ms 10064 KB Output isn't correct
12 Incorrect 64 ms 10076 KB Output isn't correct
13 Incorrect 88 ms 10076 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 45 ms 10076 KB Output isn't correct
2 Incorrect 189 ms 16300 KB Output isn't correct
3 Incorrect 73 ms 16300 KB Output isn't correct
4 Incorrect 57 ms 16300 KB Output isn't correct
5 Incorrect 57 ms 16300 KB Output isn't correct
6 Incorrect 60 ms 16300 KB Output isn't correct
7 Incorrect 55 ms 16300 KB Output isn't correct
8 Incorrect 46 ms 16300 KB Output isn't correct
9 Incorrect 160 ms 20180 KB Output isn't correct
10 Incorrect 192 ms 20180 KB Output isn't correct
11 Incorrect 118 ms 20180 KB Output isn't correct
12 Incorrect 128 ms 20180 KB Output isn't correct
13 Incorrect 92 ms 20180 KB Output isn't correct
14 Incorrect 75 ms 20180 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 71 ms 20180 KB Output isn't correct
2 Incorrect 195 ms 20180 KB Output isn't correct
3 Incorrect 140 ms 20180 KB Output isn't correct
4 Incorrect 95 ms 20180 KB Output isn't correct
5 Incorrect 97 ms 20180 KB Output isn't correct
6 Incorrect 90 ms 20180 KB Output isn't correct
7 Incorrect 112 ms 20180 KB Output isn't correct
8 Incorrect 130 ms 20180 KB Output isn't correct
9 Incorrect 149 ms 20180 KB Output isn't correct
10 Incorrect 137 ms 20180 KB Output isn't correct
11 Incorrect 155 ms 20180 KB Output isn't correct
12 Incorrect 166 ms 20180 KB Output isn't correct
13 Incorrect 173 ms 20180 KB Output isn't correct
14 Incorrect 114 ms 20180 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 119 ms 20180 KB Output isn't correct
2 Incorrect 151 ms 20180 KB Output isn't correct
3 Incorrect 115 ms 23756 KB Output isn't correct
4 Incorrect 122 ms 23756 KB Output isn't correct
5 Incorrect 137 ms 23756 KB Output isn't correct
6 Incorrect 155 ms 23756 KB Output isn't correct
7 Incorrect 146 ms 23756 KB Output isn't correct
8 Incorrect 119 ms 23868 KB Output isn't correct
9 Incorrect 72 ms 23868 KB Output isn't correct