Submission #106306

#	Time	Username	Problem	Language	Result	Execution time	Memory
106306		Pajaraja	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	278 ms	27784 KiB

ballmachine

#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() (int a,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,root;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		if(t!=0) g[t].push_back(i);
		else root=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(root);
	dfs(root);
	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 (stderr)

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:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&t,&a);
   ~~~~~^~~~~~~~~~~~~~
ballmachine.cpp:39:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(root);
  ~~~^~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5