oj.uz

Submission #1037250

# Submission time Handle Problem Language Result Execution time Memory
1037250 2024-07-28T11:31:52 Z beaconmc ČVENK (COI15_cvenk) C++14
17 / 100
 3000 ms 7616 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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