oj.uz

답안 #48429

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48429 2018-05-13T09:58:54 Z Pajaraja Ball Machine (BOI13_ballmachine) C++17
0 / 100
 186 ms 69240 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;
		}
		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 75 ms 10864 KB Output isn't correct
3 Incorrect 62 ms 12200 KB Output isn't correct
4 Incorrect 4 ms 12200 KB Output isn't correct
5 Incorrect 4 ms 12200 KB Output isn't correct
6 Incorrect 4 ms 12200 KB Output isn't correct
7 Incorrect 4 ms 12200 KB Output isn't correct
8 Incorrect 4 ms 12200 KB Output isn't correct
9 Incorrect 8 ms 12200 KB Output isn't correct
10 Incorrect 18 ms 12200 KB Output isn't correct
11 Incorrect 76 ms 13540 KB Output isn't correct
12 Incorrect 62 ms 14680 KB Output isn't correct
13 Incorrect 73 ms 15548 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 15548 KB Output isn't correct
2 Incorrect 141 ms 23856 KB Output isn't correct
3 Incorrect 69 ms 23856 KB Output isn't correct
4 Incorrect 48 ms 23856 KB Output isn't correct
5 Incorrect 48 ms 23856 KB Output isn't correct
6 Incorrect 50 ms 23856 KB Output isn't correct
7 Incorrect 46 ms 23856 KB Output isn't correct
8 Incorrect 42 ms 23856 KB Output isn't correct
9 Incorrect 140 ms 33072 KB Output isn't correct
10 Incorrect 134 ms 33072 KB Output isn't correct
11 Incorrect 106 ms 33072 KB Output isn't correct
12 Incorrect 106 ms 33072 KB Output isn't correct
13 Incorrect 87 ms 35268 KB Output isn't correct
14 Incorrect 67 ms 35268 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 35268 KB Output isn't correct
2 Incorrect 138 ms 37720 KB Output isn't correct
3 Incorrect 101 ms 37916 KB Output isn't correct
4 Incorrect 75 ms 37916 KB Output isn't correct
5 Incorrect 91 ms 37916 KB Output isn't correct
6 Incorrect 74 ms 37916 KB Output isn't correct
7 Incorrect 88 ms 40012 KB Output isn't correct
8 Incorrect 106 ms 42516 KB Output isn't correct
9 Incorrect 125 ms 42780 KB Output isn't correct
10 Incorrect 170 ms 43812 KB Output isn't correct
11 Incorrect 152 ms 46612 KB Output isn't correct
12 Incorrect 172 ms 48684 KB Output isn't correct
13 Incorrect 174 ms 51576 KB Output isn't correct
14 Incorrect 103 ms 51576 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 153 ms 51576 KB Output isn't correct
2 Incorrect 163 ms 54868 KB Output isn't correct
3 Incorrect 133 ms 62692 KB Output isn't correct
4 Incorrect 113 ms 62692 KB Output isn't correct
5 Incorrect 116 ms 62692 KB Output isn't correct
6 Incorrect 152 ms 62692 KB Output isn't correct
7 Incorrect 186 ms 62692 KB Output isn't correct
8 Incorrect 153 ms 69240 KB Output isn't correct
9 Incorrect 89 ms 69240 KB Output isn't correct