oj.uz

Submission #1037249

# Submission time Handle Problem Language Result Execution time Memory
1037249 2024-07-28T11:28:54 Z beaconmc ČVENK (COI15_cvenk) C++14
17 / 100
 0 ms 432 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<ll> A(2);
	vector<ll> B(2);
	cin >> A[0] >> A[1] >> B[0] >> B[1];
	
	vector<ll> sus = lca(A,B);


	cout << A[0]+A[1]+B[0]+B[1]-sus[0]*2-sus[1]*2;


}

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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