Submission #155454

#	Time	Username	Problem	Language	Result	Execution time	Memory
155454		Lawliet	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	361 ms	26748 KiB

ballmachine

#include <bits/stdc++.h>

#define LOG 20
#define MAX 100010

using namespace std;

int n, q;
int root;
int n1, n2;
int curTime;

int ord[MAX];
int mnSub[MAX];
int dp[LOG][MAX];

bool hasBall[MAX];

vector<int> grafo[MAX];

bool cmpSet(int a, int b) { return ord[a] < ord[b]; }
bool cmpChildren(int a, int b) { return mnSub[a] < mnSub[b]; }

set<int , decltype( &cmpSet )> nextNode( &cmpSet );

void DFSInit(int cur)
{
	mnSub[ cur ] = cur;

	for(int i = 0 ; i < grafo[ cur ].size() ; i++)
	{
		int prox = grafo[ cur ][ i ];

		DFSInit( prox );

		mnSub[ cur ] = min(mnSub[ cur ] , mnSub[ prox ]);
	}

	sort( grafo[ cur ].begin() , grafo[ cur ].end() , cmpChildren);
}

void DFSTour(int cur)
{
	for(int i = 0 ; i < grafo[ cur ].size() ; i++)
		DFSTour( grafo[cur][i] );

	ord[ cur ] = ++curTime;
}

int add(int k)
{
	int last;

	while(k-- > 0)
	{
		last = *nextNode.begin();
		nextNode.erase( nextNode.begin() );

		hasBall[ last ] = true;
	}

	return last;
}

int pop(int i)
{
	int d = 0;

	for(int k = LOG - 1 ; k >= 0 ; k--)
	{
		int jump = dp[ k ][ i ];

		if( hasBall[ jump ] )
		{
			i = jump;
			d += (1 << k);
		}
	}

	nextNode.insert( i );
	hasBall[ i ] = false;

	return d;
}

int main()
{
	scanf("%d %d",&n,&q);

	for(int i = 1 ; i <= n ; i++)
	{
		scanf("%d",&dp[0][i]);

		if(dp[0][i] == 0) root = i;

		grafo[ dp[0][i] ].push_back( i );
	}

	for(int k = 1 ; k < LOG ; k++)
	{
		for(int i = 1 ; i <= n ; i++)
		{
			int jump = dp[k - 1][ i ];

			dp[k][ i ] = dp[k - 1][ jump ];
		}
	}

	DFSInit( root );
	DFSTour( root );

	for(int i = 1 ; i <= n ; i++)
		nextNode.insert( i );

	for(int i = 1 ; i <= q ; i++)
	{
		scanf("%d %d",&n1,&n2);

		if(n1 == 1) printf("%d\n",add( n2 ));
		if(n1 == 2) printf("%d\n",pop( n2 ));
	}
}

Compilation message (stderr)

ballmachine.cpp: In function 'void DFSInit(int)':
ballmachine.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[ cur ].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void DFSTour(int)':
ballmachine.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[ cur ].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:88: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:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&dp[0][i]);
   ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n1,&n2);
   ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int add(int)':
ballmachine.cpp:62:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return last;
         ^~~~

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