Submission #753455

#	Time	Username	Problem	Language	Result	Execution time	Memory
753455		minhcool	Jousting tournament (IOI12_tournament)	C++17	100 / 100	128 ms	38488 KiB

tournament

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int n, c, r;
int k[N], s[N], e[N];

int bit[N], cur_comp[N], cnt;

// it works like this:
// we build a tree, n knights, finds lca of the position we want to choose with the nearest left&right
void upd(int id, int val){
	for(; id <= n; id += id & -id) bit[id] += val;
}

int find(int k){
	int ans = 0;
	for(int i = 19; i >= 0; i--){
		if((ans + (1LL << i)) > n) continue;
		if(bit[ans + (1LL << i)] >= k) continue;
		k -= bit[ans + (1LL << i)];
		ans += (1LL << i);
	}
	return ans + 1;
}

vector<int> Adj[N];

int anc[N][20], d[N];

void dfs(int u, int p){
	for(auto v : Adj[u]){
		if(v == p) continue;
		//cout << u << " " << v << "\n";
		anc[v][0] = u;
		for(int i = 1; i <= 19; i++) anc[v][i] = anc[anc[v][i - 1]][i - 1];
		d[v] = d[u] + 1;
		dfs(v, u);
	}
}

int lca(int x, int y){
	if(d[x] > d[y]) swap(x, y);
	int diff = d[y] - d[x];
	for(int i = 19; i >= 0; i--) if(diff & (1LL << i)) y = anc[y][i];
	if(x == y) return x;
	for(int i = 19; i >= 0; i--){
		if(anc[x][i] != anc[y][i]){
			x = anc[x][i], y = anc[y][i];
		}
	}
	return anc[x][0];
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	n = N, c = C, r = R;
	for(int i = 1; i <= c; i++){
		s[i] = S[i - 1] + 1, e[i] = E[i - 1] + 1;
	}
	for(int i = 0; i < (n - 1); i++) k[i + 1] = K[i] + 1;
	r++;
	vector<int> larger;
	larger.pb(0);
	for(int i = 1; i < n; i++) if(k[i] > r) larger.pb(i);
	larger.pb(n);
	for(int i = 1; i <= n; i++) upd(i, 1);
	int cnt = n;
	for(int i = 1; i <= n; i++) cur_comp[i] = i;
	for(int i = 1; i <= c; i++){
		cnt++;
		for(int j = s[i]; j <= e[i]; j++){
			int temp = find(j);
			Adj[cnt].pb(cur_comp[temp]);		
		}
		for(int j = s[i] + 1; j <= e[i]; j++){
			int temp = find(s[i]);
			upd(temp, -1);
		}
		int temp = find(s[i]);
		cur_comp[temp] = cnt;
	}
	dfs(cnt, cnt);
	ii answer = {-oo, oo};
	for(int pos = 1; pos <= n; pos++){
		vector<int>::iterator it = lower_bound(larger.begin(), larger.end(), pos), it2 = it;
		it2--;
		int mini = oo;
		if((*it) < n) mini = min(mini, d[pos] - d[lca(pos, (*it) + 1)] - 1);
		if((*it2) > 0) mini = min(mini, d[pos] - d[lca(pos, (*it2))] - 1);
		if(mini > answer.fi) answer = {mini, pos};
	//	cout << mini << " " << pos << "\n";
	}
	return (answer.se - 1);
 // return 0;
}

Compilation message (stderr)

tournament.cpp:18:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51