oj.uz

Submission #168857

# Submission time Handle Problem Language Result Execution time Memory
168857 2019-12-16T17:09:28 Z Lawliet Jousting tournament (IOI12_tournament) C++17
100 / 100
 182 ms 30328 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;

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

		if( BIT.query( m ) >= k ) r = m;
		else l = m + 1;
	}

	return r;
}

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 = 0;

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

		mx[i] = prof[i] - prof[l] - 1;
		if( last == 0 ) mx[i] = prof[i];

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

	last = 0;

	int ind;
	int ans = -1;

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

		int val = prof[i] - prof[l] - 1;
		if( last == 0 ) val = prof[i];

		mx[i] = min( mx[i] , val );

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

		if( i >= 2 && K[i - 2] > R ) last = 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:171:11: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
    return ind;
           ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5884 KB Output is correct
2 Correct 7 ms 6012 KB Output is correct
3 Correct 7 ms 6008 KB Output is correct
4 Correct 7 ms 6008 KB Output is correct
5 Correct 7 ms 6008 KB Output is correct
6 Correct 7 ms 6008 KB Output is correct
7 Correct 7 ms 6008 KB Output is correct
8 Correct 7 ms 6008 KB Output is correct
9 Correct 7 ms 6008 KB Output is correct
10 Correct 7 ms 6008 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6136 KB Output is correct
2 Correct 13 ms 7160 KB Output is correct
3 Correct 10 ms 6520 KB Output is correct
4 Correct 14 ms 7032 KB Output is correct
5 Correct 13 ms 7032 KB Output is correct
6 Correct 13 ms 6776 KB Output is correct
7 Correct 14 ms 7160 KB Output is correct
8 Correct 13 ms 7124 KB Output is correct
9 Correct 10 ms 6516 KB Output is correct
10 Correct 16 ms 7032 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 14456 KB Output is correct
2 Correct 182 ms 29788 KB Output is correct
3 Correct 77 ms 16548 KB Output is correct
4 Correct 173 ms 29652 KB Output is correct
5 Correct 176 ms 29636 KB Output is correct
6 Correct 180 ms 24184 KB Output is correct
7 Correct 176 ms 30284 KB Output is correct
8 Correct 182 ms 30328 KB Output is correct
9 Correct 71 ms 16376 KB Output is correct
10 Correct 93 ms 17016 KB Output is correct