oj.uz

답안 #123252

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123252 2019-06-30T21:11:38 Z gs14004 Treasure Hunt (CEOI11_tre) C++17
100 / 100
 615 ms 38104 KB 
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
const int MAXN = 400005;

int ptr = 1;
vector<int> path_info = {1};
pi par[MAXN], dep[MAXN];
int anc[19][MAXN];

void init(){}

pi get_idx_and_depth(int pos){
	auto itr = --upper_bound(path_info.begin(), path_info.end(), pos);
	int fst = (itr - path_info.begin());
	int snd = dep[fst].first + (pos - *itr);
	return pi(fst, snd);
}

void path(int a, int s){
	path_info.push_back(ptr + 1);
	ptr += s;
	auto pos = get_idx_and_depth(a);
	par[path_info.size() - 1] = pi(a, pos.first);
	dep[path_info.size() - 1] = pi(pos.second + 1, dep[pos.first].second + 1);
	anc[0][path_info.size() - 1] = pos.first;
	for(int i=1; i<19; i++){
		anc[i][path_info.size() - 1] = anc[i-1][anc[i-1][path_info.size() - 1]];
	}
}

pi getLCA(pi x, pi y){
	if(dep[y.first].second < dep[x.first].second) swap(x, y);
	int dx = dep[y.first].second - dep[x.first].second;
	if(dx > 0){
		int w = y.first;
		dx--;
		for(int i=0; i<19; i++){
			if((dx >> i) & 1) w = anc[i][w];
		}
		y = pi(par[w].second, dep[w].first - 1);
	}
	if(x.first != y.first){
		int wx = x.first, wy = y.first;
		for(int i=18; i>=0; i--){
			if(anc[i][wx] != anc[i][wy]){
				wx = anc[i][wx];
				wy = anc[i][wy];
			}
		}
		x = pi(par[wx].second, dep[wx].first - 1);
		y = pi(par[wy].second, dep[wy].first - 1);
	}
	return min(x, y);
}

int getAnc(int x, int cnt){
	auto y = get_idx_and_depth(x);
	int curUp = x - path_info[y.first];
	if(cnt <= curUp) return x - cnt;
	cnt = y.second - cnt;
	int curNd = y.first;
	for(int i=18; i>=0; i--){
		if(dep[anc[i][curNd]].first > cnt) curNd = anc[i][curNd];
	}
	y = pi(par[curNd].first, dep[curNd].first - 1);
	cnt = (y.second - cnt);
	return y.first - cnt;
}

int dig(int a, int b){
	auto v1 = get_idx_and_depth(a);
	auto v2 = get_idx_and_depth(b);
	auto l = getLCA(v1, v2);
	if(v1.second >= v2.second){
		int howUp = v1.second + v2.second - 2 * l.second;
		return getAnc(a, howUp / 2);
	}
	else{
		int howUp = v1.second + v2.second - 2 * l.second;
		return getAnc(b, (1 + howUp) / 2);
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 5 ms 732 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 525 ms 31696 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 7160 KB Output is correct
2 Correct 366 ms 21400 KB Output is correct
3 Correct 291 ms 21356 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 500 ms 21352 KB Output is correct
2 Correct 383 ms 5240 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 615 ms 21316 KB Output is correct
2 Correct 454 ms 21432 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 6772 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 456 ms 21408 KB Output is correct
2 Correct 257 ms 37988 KB Output is correct
3 Correct 292 ms 38104 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 501 ms 21356 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 440 ms 21396 KB Output is correct