Submission #362874

#	Time	Username	Problem	Language	Result	Execution time	Memory
362874		silverfish	Treasure Hunt (CEOI11_tre)	C++14	50 / 100	3009 ms	262144 KiB

Main

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

/*<DEBUG>*/
#define tem template <typename 
#define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i)
#define _op debug& operator<<
tem C > auto test(C *x) -> decltype(cerr << *x, 0LL);
tem C > char test(...);
tem C > struct itr{C begin, end; };
tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; }
struct debug{
#ifdef _LOCAL
	~debug(){ cerr << endl; }
	tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; }
	tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); }
	tem T, typename U > _op (pair<T, U> i){ 
		return *this << "< " << i.first << " , " << i.second << " >"; }
	tem T> _op (itr<T> i){
		*this <<  "{ ";
		for(auto it = i.begin; it != i.end; it++){
			*this << " , " + (it==i.begin?2:0) << *it;
		}
		return *this << " }";
	}
#else
tem T> _op (const T&) { return *this; }
#endif 
};

string _ARR_(int* arr, int sz){
	string ret = "{ " + to_string(arr[0]); 
	for(int i = 1; i < sz; i++) ret += " , " +  to_string(arr[i]);
	ret += " }"; return ret;
}

#define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]"
/*</DEBUG>*/

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pb push_back
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define TC int __TC__; cin >> __TC__; while(__TC__--)
#define ar array

const int INF = 1e9 + 7, N = 1e6;

struct parent{
	int id, type, cost, from; 
};

int compress = 1;
unordered_map<int, int> mp;
int up[21][2][N];
set<int> nodes;
int d[N], cur=1;
parent p[N];

// up[2^i][0 : to, 1 : cost][from]
void upd_lift(int u){
	if(mp[u] == 0) mp[u] = compress++;
	int cu = mp[u];
	int cost = p[u].cost;
	up[0][0][cu] = p[u].id;
	up[0][1][cu] = p[u].cost;

	for(int i = 1; i <= 20; ++i){
//							how much  what	from where
		up[i][0][cu] =        up[i-1]  [0]  [up[i-1][0][cu]];
		up[i][1][cu] = cost + up[i-1]  [1]  [up[i-1][0][cu]];
		cost = up[i][1][cu];
	}
	return;
}

void init(){
	d[1] = 0;
	nodes.insert(1);
	p[1].id = 1;
	p[1].cost = 0;
	p[1].type = 2;
	upd_lift(1);
	return;
}


//parent edge type:
// 0 : range
// 1 : intersection
// 2 : normal



void path(int a, int s){
	debug() << exp(a) exp(s);
	//auto it = nodes.lower_bound(a);	


	++cur;
	p[cur].id = a;
	p[cur].type = 2;
	p[cur].cost = 1;
	p[cur].from = cur;
	d[cur] = d[a] + 1;

	upd_lift(cur);

	int cur2 = cur;
	for(; cur < cur2+s-1; ++cur){
		p[cur+1].id = cur;
		p[cur+1].type = 2;
		p[cur+1].cost = 1;
		p[cur+1].from = cur;
		d[cur+1] = d[cur] + 1;
		
		upd_lift(cur+1);
	}

	/*
	if(*it > a){
		--it;
		// *it < a
		//adj[*it].pb({cur+1, 1, a});

		p[cur+1].from = a;
		p[cur+1].type = 1;
		p[cur+1].id = *it;
		p[cur+1].cost = *it - a;
		d[cur+1] = d[*it] + 1;
		nodes.insert(cur+1);
		
		upd_lift(cur+1);
	}else{
		// *it == a

		//adj[a].pb({cur+1, 2, a});

		p[cur+1].from = a;
		p[cur+1].type = 2;
		p[cur+1].id = a;
		p[cur+1].cost = 1;
		d[cur+1] = d[a] + 1;
		nodes.insert(cur+1);

		upd_lift(cur+1);
	}

	if(s >= 2){
		//adj[cur+1].pb({cur+s, (s == 2 ? 2 : 0), cur+1});

		p[cur+s].from = cur+1;
		p[cur+s].type = (s == 2 ? 2 : 0);
		p[cur+s].id = cur+1;
		p[cur+s].cost = s-1;
		d[cur+s] = d[cur+1] + 1;
		nodes.insert(cur+s);

		upd_lift(cur+s);

	}
	*/
	return;
}

int dist1, dist2;
ar<int, 2> lca;
// lca[0] : node lca
// lca[1] : real lca

ar<int,2> go_up_nodes(int u, int dist){
	int cost = 0;
	for(int i = 0; i <= 20; ++i){
		if(dist & (1 << i)){
			cost += up[i][1][mp[u]];
			u = up[i][0][mp[u]];
		}
	}
	return {u, cost};
}

int find_path_len(int a, int b){
	dist1 = dist2 = 0;
	int cost = 0;
	bool swapped = 0;

	if(d[a] > d[b]) {
		swap(a, b);
		swapped = 1;
	}

	ar<int,2> temp = go_up_nodes(b, d[b] - d[a]);
	b = temp[0];
	dist2 += temp[1];
	debug() << exp(dist2);

	//if lca is a
	if(a == b){
		lca = {a, -1};
		cost = dist2;
		dist1 = 0;
		if(swapped) swap(dist1, dist2);
		return cost;
	}

	for(int i = 20; i >= 0; --i){
		int u = up[i][0][mp[a]];
		if(u == 0) u = 1;
		int v = go_up_nodes(b, d[b]-d[u])[0];

		if(v != u){
			cost += up[i][1][mp[a]];
			a = u;
		}
	}

	cost += up[0][1][mp[a]];
	a = up[0][0][mp[a]];
	debug() << exp(a) exp(cost);
	dist1 = cost;

	debug() << exp(a) exp(b);
	debug() << exp(dist1) exp(dist2);

	temp = go_up_nodes(b, d[b] - d[a]);
	b = temp[0];
	dist2 += temp[1];

	cost += dist2;
	if(swapped) swap(dist1, dist2);
	return cost;
}

//parent edge type:
// 0 : range
// 1 : intersection
// 2 : normal
int go_up(int u, int dist){
	if(dist == 0) return u;
	int cost = 0;

	for(int i = 20; i >= 0; --i){
		if(cost + up[i][1][mp[u]] < dist){
			cost += up[i][1][mp[u]];
			u = up[i][0][mp[u]];
		}
	}

	if(p[u].type != 2){
		return p[u].from + (dist - cost) - 1;
	}else{
		return p[u].id;
	}
}

// dist1 : a to lca
// dist2 : lca to b
int find_node(int a, int b, int dist){
	if(dist <= dist1){
		return go_up(a, dist);
	}else{
		return go_up(b, dist2 + dist1 - dist);
	}
}

int dig(int a, int b){
	debug() << exp(a) exp(b);
	return find_node(a, b, find_path_len(a, b)/2);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10