Submission #120932

#	Time	Username	Problem	Language	Result	Execution time	Memory
120932		KieranHorgan	Jousting tournament (IOI12_tournament)	C++17	49 / 100	1060 ms	14456 KiB

tournament

// #include "grader.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> AdjList[200005];
int sz[200005];
int curNode = 1;
int N, C, R, *K, *S, *E;
int actualIdxToNode[100005];
int nodeToActualIdx[200005];

void addNode(int id, int curIdx, int idxToAdd, int sizeToAdd) {
	if(AdjList[id].empty()) {
		for(int i = 0; i < sizeToAdd; i++) {
			AdjList[id].push_back(++curNode);
			sz[curNode] = 1;
		}
	} else {
		for(auto v: AdjList[id]) {
			if(curIdx + sz[v] <= idxToAdd) {
				curIdx += sz[v];
			} else {
				addNode(v, curIdx, idxToAdd, sizeToAdd);
				break;
			}
		}
	}
	sz[id] = 0;
	for(auto v: AdjList[id])
		sz[id] += sz[v];
}

int curActualIdx = 0;
void assignIdx(int id) {
	if(sz[id] == 1) {
		actualIdxToNode[curActualIdx] = id;
		nodeToActualIdx[id] = curActualIdx++;
		return;
	}
	for(auto v: AdjList[id])
		assignIdx(v);
}

int depth[200005];
int kthAncestor[200005][20];
void getDepth(int u, int d) {
	depth[u] = d;
	for(auto v: AdjList[u]) {
		kthAncestor[v][0] = u;
		getDepth(v, d-1);
	}
}

void calcKthAncestor() {
	kthAncestor[1][0] = 0;
	for(int i = 1+1; i <= curNode; i++)
		for(int j = 1; j < 20; j++) {
			kthAncestor[i][j] = kthAncestor[kthAncestor[i][j-1]][j-1];
			if(kthAncestor[i][j]==0) break;
		}
}

int lca(int a, int b) {
	for(int j = 31-__builtin_clz(C-depth[a]); j >= 0; j--)
		if(depth[a] + (1<<j) <= depth[b])
			a = kthAncestor[a][j];
	for(int j = 31-__builtin_clz(C-depth[b]); j >= 0; j--)
		if(depth[b] + (1<<j) <= depth[a])
			b = kthAncestor[b][j];
	for(int j = 31-__builtin_clz(C-depth[a]); j >= 0; j--)
		if(kthAncestor[a][j] != kthAncestor[b][j]) {
			a = kthAncestor[a][j];
			b = kthAncestor[b][j];
		}
	if(a != b) {
		a = kthAncestor[a][0];
		b = kthAncestor[b][0];
	}
	return a;
}

int closestToLeft[100005];
int closestToRight[100005];

int GetBestPosition(int N_, int C_, int R_, int *K_, int *S_, int *E_) {
	N=N_, C=C_, R=R_;
	K=K_, S=S_, E=E_;
	sz[1] = 1;
	for(int i = C-1; i >= 0; i--)
		addNode(1, 0, S[i], E[i]-S[i]+1);
	assignIdx(1);

	getDepth(1,C);
	calcKthAncestor();

	closestToLeft[0] = -1;
	for(int i = 1; i <= N; i++) {
		closestToLeft[i] = closestToLeft[i-1];
		if(K[i-1] > R)
			closestToLeft[i] = i-1;
	}

	closestToRight[N-1] = -1;
	for(int i = N-1-1; i >= 0; i--) {
		closestToRight[i] = closestToRight[i+1];
		if(K[i+1-1] > R)
			closestToRight[i] = i+1;
	}

	int ans = -1;
	int pos = -1;
	for(int i = 0; i < N; i++) {
		int a = 0;
		if(closestToLeft[i] == -1) {
			a = C-depth[actualIdxToNode[i]];
		} else {
			a = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToLeft[i]])]-depth[actualIdxToNode[i]]-1;
		}
		int b = 0;
		if(closestToRight[i] == -1) {
			b = C-depth[actualIdxToNode[i]];
		} else {
			b = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToRight[i]])]-depth[actualIdxToNode[i]]-1;
		}

		if(min(a,b) > ans) {
			ans = min(a,b);
			pos = i;
		}
	}

	return pos;
}

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