oj.uz

Submission #155453

# Submission time Handle Problem Language Result Execution time Memory
155453 2019-09-28T11:50:17 Z Lawliet Ball Machine (BOI13_ballmachine) C++17
0 / 100
 1000 ms 22948 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( 1 );
	DFSTour( 1 );

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

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 2808 KB Time limit exceeded
2 Execution timed out 1030 ms 9080 KB Time limit exceeded
3 Incorrect 63 ms 9468 KB Output isn't correct
4 Execution timed out 1066 ms 2808 KB Time limit exceeded
5 Execution timed out 1073 ms 2876 KB Time limit exceeded
6 Execution timed out 1076 ms 2808 KB Time limit exceeded
7 Execution timed out 1058 ms 2808 KB Time limit exceeded
8 Execution timed out 1082 ms 2808 KB Time limit exceeded
9 Execution timed out 1080 ms 3192 KB Time limit exceeded
10 Execution timed out 1064 ms 4472 KB Time limit exceeded
11 Execution timed out 1059 ms 9208 KB Time limit exceeded
12 Incorrect 63 ms 9464 KB Output isn't correct
13 Execution timed out 1079 ms 9080 KB Time limit exceeded

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 7100 KB Output isn't correct
2 Execution timed out 1067 ms 16444 KB Time limit exceeded
3 Incorrect 76 ms 12276 KB Output isn't correct
4 Execution timed out 1069 ms 6008 KB Time limit exceeded
5 Execution timed out 1085 ms 5880 KB Time limit exceeded
6 Execution timed out 1076 ms 5752 KB Time limit exceeded
7 Execution timed out 1072 ms 5624 KB Time limit exceeded
8 Incorrect 49 ms 7164 KB Output isn't correct
9 Execution timed out 1055 ms 19448 KB Time limit exceeded
10 Execution timed out 1075 ms 16376 KB Time limit exceeded
11 Execution timed out 1081 ms 12664 KB Time limit exceeded
12 Execution timed out 1079 ms 12408 KB Time limit exceeded
13 Incorrect 97 ms 15992 KB Output isn't correct
14 Incorrect 69 ms 12172 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 10488 KB Time limit exceeded
2 Execution timed out 1063 ms 16236 KB Time limit exceeded
3 Execution timed out 1078 ms 14580 KB Time limit exceeded
4 Execution timed out 1078 ms 11128 KB Time limit exceeded
5 Execution timed out 1074 ms 10756 KB Time limit exceeded
6 Execution timed out 1079 ms 10744 KB Time limit exceeded
7 Execution timed out 1074 ms 13816 KB Time limit exceeded
8 Execution timed out 1018 ms 14712 KB Time limit exceeded
9 Execution timed out 1059 ms 13048 KB Time limit exceeded
10 Execution timed out 1081 ms 12536 KB Time limit exceeded
11 Execution timed out 1072 ms 14840 KB Time limit exceeded
12 Execution timed out 1049 ms 16120 KB Time limit exceeded
13 Execution timed out 1077 ms 16676 KB Time limit exceeded
14 Execution timed out 1083 ms 12176 KB Time limit exceeded

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1031 ms 13036 KB Time limit exceeded
2 Execution timed out 1067 ms 17016 KB Time limit exceeded
3 Incorrect 163 ms 22904 KB Output isn't correct
4 Execution timed out 1068 ms 13048 KB Time limit exceeded
5 Execution timed out 1069 ms 12664 KB Time limit exceeded
6 Incorrect 210 ms 19688 KB Output isn't correct
7 Execution timed out 1067 ms 17116 KB Time limit exceeded
8 Incorrect 147 ms 22948 KB Output isn't correct
9 Incorrect 71 ms 12148 KB Output isn't correct