oj.uz

Submission #123250

# Submission time Handle Problem Language Result Execution time Memory
123250 2019-06-30T20:53:16 Z gs14004 Treasure Hunt (CEOI11_tre) C++17
40 / 100
 4000 ms 7496 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];

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);
}

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;
	for(int i=0; i<dx; i++){
		y = pi(par[y.first].second, dep[y.first].first - 1);
	}
	while(x.first != y.first){
		x = pi(par[x.first].second, dep[x.first].first - 1);
		y = pi(par[y.first].second, dep[y.first].first - 1);
	}
	return min(x, y);
}

int getAnc(int x, int cnt){
	auto y = get_idx_and_depth(x);
	while(cnt > 0){
		int curUp = x - path_info[y.first];
		if(cnt <= curUp) return x - cnt;
		cnt -= curUp + 1;
		x = par[y.first].first;
		y = get_idx_and_depth(x);
	}
	return x;
}

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 7496 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4019 ms 1164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4011 ms 3800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4024 ms 1660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 3000 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4035 ms 2668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4050 ms 4460 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4051 ms 4288 KB Time limit exceeded