oj.uz

Submission #168849

# Submission time Handle Problem Language Result Execution time Memory
168849 2019-12-16T16:45:40 Z Lawliet Jousting tournament (IOI12_tournament) C++17
0 / 100
 188 ms 31424 KB 
#include <bits/stdc++.h>

using namespace std;

const int LOG = 20;
const int MAXN = 200010;

class FenwickTree
{
	public:

		void update(int i, int v)
		{
			for( ; i < MAXN ; i += i & -i )
				BIT[ i ] += v;
		}

		int query(int i)
		{
			int ans = 0;

			for( ; i > 0 ; i -= i & -i )
				ans += BIT[ i ];

			return ans;
		}

		FenwickTree() { memset( BIT , 0 , sizeof(BIT) ); }

	private:

		int BIT[MAXN];
};

int n;
int cntNode;

int mx[MAXN];
int prof[MAXN];
int dp[LOG][MAXN];
int virtualNode[MAXN];

vector< int > adj[MAXN];

FenwickTree BIT;

void DFS(int cur)
{
	for(int k = 1 ; k < LOG ; k++)
		dp[k][cur] = dp[k - 1][ dp[k - 1][cur] ];

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

		prof[ viz ] = prof[ cur ] + 1;

		DFS( viz );
	}
}

int getKthKnight(int k)
{
	int l = 1;
	int r = n;

	if( BIT.query( 1 ) == k ) return 1;

	while( l < r )
	{
		int m = ( l + r )/2;
		if( l == r - 1 ) m = r;

		if( BIT.query( m ) < k ) l = m;
		else r = m - 1;
	}

	return l + 1;
}

int LCA(int U, int V)
{
	if( prof[U] < prof[V] ) swap( U , V );

	int d = prof[U] - prof[V];

	for(int k = 0 ; k < LOG ; k++)
		if( d & (1 << k) ) U = dp[k][U];

	if( U == V ) return U;

	for(int k = LOG - 1 ; k >= 0 ; k--)
	{
		if( dp[k][U] != dp[k][V] )
		{
			U = dp[k][U];
			V = dp[k][V];
		}
	}

	return dp[0][U];
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) 
{
	n = N;
	cntNode = n;

	for(int i = 1 ; i <= n ; i++)
	{
		virtualNode[i] = i;
		BIT.update( i , 1 );
	}

	for(int i = 0 ; i < C ; i++)
	{
		cntNode++;
		E[i]++; S[i]++;

		int sz = E[i] - S[i] + 1;

		for(int j = 0 ; j < sz ; j++)
		{
			int cur = getKthKnight( S[i] );

			dp[0][ virtualNode[cur] ] = cntNode;
			adj[ cntNode ].push_back( virtualNode[cur] );

			if( j != sz - 1 ) BIT.update( cur , -1 );
		}

		int last = getKthKnight( S[i] );

		virtualNode[ last ] = cntNode;
	}

	DFS( cntNode );

	int last = cntNode;

	for(int i = 1 ; i <= n ; i++)
	{
		int l = LCA( i , last );

		mx[i] = prof[i] - prof[l] - 1;
		if( K[i] > R ) last = i;
	}

	last = cntNode;

	int ind;
	int ans = -1;

	for(int i = n ; i > 0 ; i--)
	{
		int l = LCA( i , last );

		mx[i] = min( mx[i] , prof[i] - prof[l] - 1 );
		if( K[i] > R ) last = i;

		if( ans <= mx[i] )
		{
			ind = i - 1;
			ans = mx[i];
		}
	}

  	return ind;
}

Compilation message

tournament.cpp: In function 'void DFS(int)':
tournament.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:168:11: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
    return ind;
           ^~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6136 KB Output is correct
2 Correct 13 ms 7160 KB Output is correct
3 Incorrect 10 ms 6520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 14412 KB Output is correct
2 Correct 188 ms 31424 KB Output is correct
3 Incorrect 79 ms 17136 KB Output isn't correct
4 Halted 0 ms 0 KB -