Submission #225477

#	Time	Username	Problem	Language	Result	Execution time	Memory
225477		staniewzki	Jousting tournament (IOI12_tournament)	C++17	32 / 100	136 ms	33016 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif

template<class T> int size(T && a) { return (int) a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

struct Tree {
	vector<int> tree;
	int sz = 1;

	Tree(int n) {
		while(sz < n) sz *= 2;
		tree.resize(sz * 2);
	}

	void update(int pos, int val) {
		tree[pos += sz] = val;
		while(pos /= 2)
			tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
	}

	int query(int k) {
		int pos = 1;
		while(pos < sz) {
			pos *= 2;
			if(k >= tree[pos])
				k -= tree[pos], pos++;
		}
		return pos - sz;
	}
};

struct JumpPtr {
	int LOG = 20;
	vector<vector<int>> &graph, jump;
	vector<int> par, dep;
	void par_dfs(int v) {
		for(int u : graph[v]) {
			if(u != par[v]) {
				par[u] = v;
				dep[u] = dep[v] + 1;
				par_dfs(u);
			}
		}
	}
	JumpPtr(vector<vector<int>> &graph, int root = 0) : graph(graph) {
		int n = size(graph);
		par.resize(n, -1);
		dep.resize(n);
		par_dfs(root);
		jump.resize(LOG, vector<int>(n));
		jump[0] = par;
		FOR(i, 1, LOG - 1) REP(j, n)
			jump[i][j] = jump[i - 1][j] == -1 ? -1 : jump[i - 1][jump[i - 1][j]];
	}
	int jump_up(int v, int k) {
		for(int i = LOG - 1; i >= 0; i--)
			if(k & (1 << i))
				v = jump[i][v];
		return v;
	}
	int lca(int a, int b) {
		if(dep[a] < dep[b]) swap(a, b);
		int delta = dep[a] - dep[b];
		a = jump_up(a, delta);
		if(a == b) return a;
		
		for(int i = LOG - 1; i >= 0; i--) {
			if(jump[i][a] != jump[i][b]) {
				a = jump[i][a];
				b = jump[i][b];
			}
		}
		return par[a];		
	}
	int dst(int v, int u) { 
		return dep[v] - dep[u];
	}
};

int GetBestPosition(int N, int C, int R, int K[], int S[], int E[]) {
	vector<int> node(N);
	vector<vector<int>> graph(N + C);
	Tree tree(N);
	REP(i, N) {
		node[i] = i;
		tree.update(i, true);
	}

	REP(i, C) {
		int v = N + i;
		FOR(j, S[i], E[i]) {
			int q = tree.query(j);
			int u = node[q];
			graph[v].emplace_back(u);
		}

		for(int j = E[i]; j >= S[i]; j--) {
			int q = tree.query(j);
			if(j == S[i])
				node[q] = v;
			else
				tree.update(q, false);
		}
	}

	JumpPtr ptr(graph, N + C - 1);
		
	vector<int> larger;
	REP(i, N - 1)
		if(K[i] > R)
			larger.emplace_back(i);

	PII ans = {0, -1};
	int cur = 0;
	REP(i, N) {
		int len = 1e9;
		if(cur != 0) {
			int v = larger[cur - 1];
			int lca = ptr.lca(i, v);
			len = min(len, ptr.dst(i, lca));
		}
		if(cur < size(larger)) {
			int v = larger[cur] + 1;
			int lca = ptr.lca(i, v);
			len = min(len, ptr.dst(i, lca));
			if(i == v) cur++;
		}
		ans = max(ans, {len, -i});
	}

	return -ans.ND;
}

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