oj.uz

Submission #561472

# Submission time Handle Problem Language Result Execution time Memory
561472 2022-05-12T22:38:57 Z CaroLinda Jousting tournament (IOI12_tournament) C++14
0 / 100
 23 ms 7364 KB 
#include <bits/stdc++.h>

#define debug printf
#define ff first
#define ss second
#define mk make_pair
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define pii pair<int,int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())

const int LOG = 20 ;
const int MAXN = 1e5+10 ;

using namespace std ;

int currNode ;
int l[MAXN*2] , r[MAXN*2] , lvl[MAXN*2] ;
int dsu[MAXN*2] ;
int dp[LOG][MAXN*2] ;

int find(int x){ return dsu[x] = (x == dsu[x]) ? x : find(dsu[x]) ; }

int getLca(int x, int y){

	if(x == y) return x ;

	for(int i = LOG-1 ; i >= 0 ; i-- ){
		if(!dp[i][x] || dp[i][x] == dp[i][y]) continue ;
		x = dp[i][x] ;
		y = dp[i][y] ;
	}
	return dp[0][x] ;
}

int GetBestPosition(int N, int C, int R, int *K, int *s, int *e) 
{

	for(int i =0  ; i < N; i++ ){
		dsu[i] = i ;
		l[i] = r[i] = i ;
	}

	currNode = N-1 ;

	for(int i= 0 ; i < C ; i++ ){
		
		int K = e[i]-s[i]+1 , cur = s[i] ;
		
		dsu[++currNode] = currNode ;

		vector<int> vec ;

		while(K--){
			vec.push_back(find(cur)) ;
			cur = r[find(cur)]+1 ;
		}

		l[currNode] = l[ vec[0] ] ;
		r[currNode] = r[ vec.back() ] ;

		for(int i= 0 ; i < sz(vec) ; i++ ){
			dsu[ vec[i] ] = currNode ;
			dp[0][vec[i]] = currNode ;
		}

	}

	for(int i = currNode-1 ; i >= 0 ; i-- )
		lvl[i] = lvl[ dp[0][i] ]+1 ;

	for(int i = 1 ; i < LOG ; i++ )
		for(int j = 0 ; j <= currNode ; j++ )
			if(dp[i-1][j]) dp[i][j] = dp[i-1][dp[i-1][j]] ;

	vector<int> maiorDir ;
	for(int i = N-2 ; i >= 0 ; i-- ){
		if(K[i] > R) maiorDir.push_back(i) ;
	}

	int idEsq = -1 ;
	int ans = 0 , pos = 0 ;

	for(int i = 0 ; i < N ; i++ ){

		int idRight = -1 ;

		while(!maiorDir.empty() && maiorDir.back() < i ) maiorDir.pop_back() ;

		if(!maiorDir.empty()) idRight = maiorDir.back() ;

		int ans1 = lvl[i] , ans2 = lvl[i] ;

		if(idEsq != -1 ) ans1 -= lvl[getLca(idEsq,i)] ;
		if(idRight != -1 ) ans2 -= lvl[getLca(idRight+1, i)] ;

		if(min(ans1,ans2) > ans){
			pos = i ;
			ans = min(ans1, ans2) ;
		}

		if(K[i] > R) idEsq = i ;

	}

	/*for(int i = 0 ; i < currNode ; i++ ){
		cout << i << " -> " << dp[0][i] << endl ;
	} */

	return pos ;

}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:51:7: warning: operation on 'currNode' may be undefined [-Wsequence-point]
   51 |   dsu[++currNode] = currNode ;
      |       ^~~~~~~~~~
tournament.cpp:51:7: warning: operation on 'currNode' may be undefined [-Wsequence-point]

Subtask #1
0 / 17.0

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

Subtask #2
0 / 32.0

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

Subtask #3
0 / 51.0

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