oj.uz

Submission #155454

# Submission time Handle Problem Language Result Execution time Memory
155454 2019-09-28T11:51:32 Z Lawliet Ball Machine (BOI13_ballmachine) C++17
100 / 100
 361 ms 26748 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 187 ms 13432 KB Output is correct
3 Correct 104 ms 12920 KB Output is correct
4 Correct 4 ms 2812 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 5 ms 3064 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct
9 Correct 12 ms 3448 KB Output is correct
10 Correct 37 ms 5280 KB Output is correct
11 Correct 181 ms 13304 KB Output is correct
12 Correct 105 ms 12920 KB Output is correct
13 Correct 151 ms 13304 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7172 KB Output is correct
2 Correct 242 ms 21840 KB Output is correct
3 Correct 126 ms 17524 KB Output is correct
4 Correct 95 ms 8952 KB Output is correct
5 Correct 96 ms 8928 KB Output is correct
6 Correct 88 ms 8952 KB Output is correct
7 Correct 89 ms 8032 KB Output is correct
8 Correct 51 ms 7160 KB Output is correct
9 Correct 221 ms 22008 KB Output is correct
10 Correct 282 ms 21860 KB Output is correct
11 Correct 199 ms 22008 KB Output is correct
12 Correct 230 ms 20088 KB Output is correct
13 Correct 162 ms 23332 KB Output is correct
14 Correct 122 ms 17484 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 12536 KB Output is correct
2 Correct 287 ms 20572 KB Output is correct
3 Correct 214 ms 21724 KB Output is correct
4 Correct 223 ms 18424 KB Output is correct
5 Correct 176 ms 18040 KB Output is correct
6 Correct 206 ms 18152 KB Output is correct
7 Correct 173 ms 16860 KB Output is correct
8 Correct 195 ms 21716 KB Output is correct
9 Correct 278 ms 22592 KB Output is correct
10 Correct 279 ms 22136 KB Output is correct
11 Correct 264 ms 22136 KB Output is correct
12 Correct 319 ms 20532 KB Output is correct
13 Correct 346 ms 26748 KB Output is correct
14 Correct 292 ms 18368 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 22760 KB Output is correct
2 Correct 265 ms 20572 KB Output is correct
3 Correct 181 ms 25920 KB Output is correct
4 Correct 300 ms 22816 KB Output is correct
5 Correct 292 ms 22332 KB Output is correct
6 Correct 213 ms 21496 KB Output is correct
7 Correct 361 ms 20572 KB Output is correct
8 Correct 222 ms 25728 KB Output is correct
9 Correct 154 ms 17652 KB Output is correct