Submission #1037250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037250		beaconmc	ČVENK (COI15_cvenk)	C++14	17 / 100	3059 ms	7616 KiB

cvenk

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;



vector<ll> lca(vector<ll> a, vector<ll> b){
	if (a[0]+a[1] < b[0] + b[1]) swap(a,b);
	map<vector<ll>, vector<ll>> prev;
	set<vector<ll>> stuff;
	stuff.insert(a);
	prev[a] = {-1,-1};



	while (a[0] != 0 || a[1] != 0){
		
		ll fira=1000, firb=1000;
		FOR(i,0,31) if ((1<<i)&a[0]){fira = i; break;}
		FOR(i,0,31) if ((1<<i)&a[1]){firb = i; break;}



		if (fira > firb){
			vector<ll> old = a;
			if (fira==1000){
				a = {0,0};
			}
			else a[1] -= (a[1] % (1<<fira));
			
			
			stuff.insert(a);
			prev[a] = old;
		}else{
			vector<ll> old = a;
			if (firb==1000){
				a = {0,0};
			}
			else a[0] -= (a[0] % (1<<firb));
			stuff.insert(a);
			prev[a] = old;
		}
	}



	if (stuff.count(b)) return b;

	while (b[0] != 0 || b[1] != 0){
		ll fira=1000, firb=1000;
		FOR(i,0,31) if ((1<<i)&b[0]){fira = i; break;}
		FOR(i,0,31) if ((1<<i)&b[1]){firb = i; break;}


		if (fira > firb){
			vector<ll> old = b;
			if (fira==1000) b = {0,0};
			else b[1] -= (b[1] % (1<<fira));
			if (stuff.count(b)){
				if ((b[0] == old[0] && old[0] == prev[b][0]) || (b[1] == old[1] && old[1] == prev[b][1])) return old;
				return b;
			}

		}else{
			vector<ll> old = b;
			if (firb==1000) b = {0,0};
			else b[0] -= (b[0] % (1<<firb));
			if (stuff.count(b)){
				if ((b[0] == old[0] && old[0] == prev[b][0]) || (b[1] == old[1] && old[1] == prev[b][1])) return old;
				return b;
			}
		}
	}


	return {};
}
int main(){
	ll n;
	cin >> n;
	vector<vector<ll>> stuff;
	FOR(i,0,n){
		ll a,b;
		cin >> a >> b;
		stuff.push_back({a,b});
	}
	ll ans = 1000000000000000;
	for (auto&k : stuff){
		ll temp = 0;
		for (auto&i : stuff){
			vector<ll> sus = lca(k, i);
			temp += i[0]+i[1]+k[0]+k[1] - sus[0]*2 - sus[1]*2;
		}
		ans = min(ans, temp);
	}
	cout << ans << endl;



}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40