Submission #274704

#	Time	Username	Problem	Language	Result	Execution time	Memory
274704		amoo_safar	Jousting tournament (IOI12_tournament)	C++17	100 / 100	170 ms	32120 KiB

tournament

// That's How much we have in common
#include <bits/stdc++.h>

#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

const int N = 2e5 + 10;
const int Log = 20;

int n, par[N], la;
vector<int> G[N];

int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Unite(int u, int v){
	u = Find(u); v = Find(v);
	assert(u != v);
	par[u] = v;
	G[v].pb(u);
}
int fen[N];
void Add(int idx, int d){
	for(; idx < N; idx += idx & (-idx))
		fen[idx] += d;
}
int BinS(int x){
	int res = 0;
	int res2;
	for(int l = Log - 1; l >= 0; l--){
		res2 = res | (1 << l);
		if(res2 >= N) continue;
		if(fen[res2] < x){
			x -= fen[res2];
			res = res2;
		}
	}
	assert(res + 1 <= n);
	return res + 1;
}
int sp[Log][N], dep[N];
void DFS(int u, int p, int d = 0){
	sp[0][u] = p;
	dep[u] = d;
	for(int l = 1; l < Log; l++)
		sp[l][u] = sp[l - 1][sp[l - 1][u]];
	for(auto adj : G[u]){
		DFS(adj, u, d + 1);
	}
}
int Lift(int u, int h){
	for(int l = 0; l < Log; l++)
		if(h >> l & 1)
			u = sp[l][u];
	return u;
}
int LCA(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	u = Lift(u, dep[u] - dep[v]);
	if(u == v) return u;
	for(int l = Log - 1; l >= 0; l--){
		if(sp[l][u] != sp[l][v]){
			u = sp[l][u];
			v = sp[l][v];
		}
	}
	assert(u != v);
	assert(sp[0][u] == sp[0][v]);
	return sp[0][u];
}
int GetBestPosition(int _n, int C, int R, int *K, int *S, int *E) {
	memset(fen, 0, sizeof fen);
	iota(par, par + N, 0);
	n = _n;
	for(int i = 1; i <= n; i++) G[i].clear();
	la = n;
	
	for(int i = 1; i <= n; i++) Add(i, 1);
	vector<int> V;
	int pos;
	for(int i = 0; i < C; i++){
		int len = E[i] - S[i] + 1;
		V.clear();
		for(int j = 0; j < len; j++){
			pos = BinS(S[i] + 1);
			Add(pos, -1);
			V.pb(pos);
		}
		Add(V[0], 1);

		la ++;
		for(auto x : V) Unite(x, la);
	}
	//cerr << "# " << la << '\n';
	DFS(la, la);
	//cerr << "dep : ";
	//for(int i = 1; i <= n; i++) cerr << dep[i] << ' ';
	//cerr << '\n';

	V.clear();
	for(int i = 0; i < n - 1; i++)
		if(K[i] > R)
			V.pb(i + 1);
	if(V.empty()){
		int mx = *max_element(dep + 1, dep + n + 1);
		for(int i = 1; i <= n; i++) if(dep[i] == mx) return i - 1;
		return n - 1;
	}

	int la = -1;
	int nw = n;
	int ans = -1, bans = n;
	while(nw){
		int res = n;
		if(la != -1)
			res = min(res, dep[nw] - dep[LCA(nw, la)] - 1);
		if(!V.empty())
			res = min(res, dep[nw] - dep[LCA(nw, V.back())] - 1);
		//cerr << "WTF : " << nw << ' ' << res << '\n';
		if(ans <= res){
			ans = res;
			bans = nw;
		}

		nw --;
		if(!V.empty() && V.back() == nw){
			la = nw + 1;
			V.pop_back();
		}
	}
	return bans - 1;
}

/*
5 3 3
1
0
2
4
1 3
0 1
0 1

*/

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