Submission #846447

#	Time	Username	Problem	Language	Result	Execution time	Memory
846447		vjudge1	ČVENK (COI15_cvenk)	C++17	0 / 100	24 ms	2516 KiB

cvenk

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

array<int,2> lca(array<int,2> a,array<int,2> b){
	vector<array<int,2>> par_a;
	vector<array<int,2>> par_b;

	par_a.pb(a);
	par_b.pb(b);

	while(a[0]>0 && a[1]>0 ){
       int x = a[0]&-a[0];
       int y = a[1]&-a[1];
       if(x>y){
       	 a[1]-=y;
         par_a.pb(a);
        }
       else{
       	 a[0]-=x;
       	 par_a.pb(a);
       }
	}

	while(a[0]>0){
		a[0]-=a[0]&-a[0];
       	par_a.pb(a);
	}

	while(a[1]>0){
		a[1]-=a[1]&-a[1];
       	par_a.pb(a);
	}

	while(b[0]>0 && b[1]>0 ){
       int x = b[0]&-b[0];
       int y = b[1]&-b[1];
       if(x>y){
       	 b[1]-=y;
         par_b.pb(b);
        }
       else{
       	 b[0]-=x;
       	 par_b.pb(b);
       }
	}

	while(b[0]>0){
		b[0]-=b[0]&-b[0];
       	par_b.pb(b);
	}

	while(b[1]>0){
		b[1]-=b[1]&-b[1];
       	par_b.pb(b);
	}
  
  map<int,int> mpr;
  map<int,int> mpc;

  for(int i=0;i<sz(par_b);i++){
  	auto x = par_b[i];
  	if(!mpr.count(x[0])) mpr[x[0]]= i;
  	if(!mpc.count(x[1])) mpc[x[1]]= i; 
  }

  array<int,2> res={0,0};

  for(int i=0;i<sz(par_a);i++){
  	auto x = par_a[i];
  	if(mpr.count(x[0])){
      array<int,2> cur = {x[0],min(x[1],par_b[mpr[x[0]]][1])};
      res=max(res,cur);
      break;
  	}
  }

  for(int i=0;i<sz(par_a);i++){
  	auto x = par_a[i];
  	if(mpc.count(x[1])){
      array<int,2> cur = {min(x[0],par_b[mpc[x[1]]][0]),x[1]};
      res=max(res,cur);
      break;
  	}
  }
  
  return res;
}

void solve(){
  int n;
  cin >> n;
  vector<array<int,2>> v;
  for(int i=0;i<n;i++){
  	int a,b;
  	cin >> a >> b;
  	v.pb({a,b});
  }

  array<int,2> xd = lca(v[0],v[1]);

  int ans=0;

  ans+=v[0][0]-xd[0]+v[0][1]-xd[1];
  ans+=v[1][0]-xd[0]+v[1][1]-xd[1];

  cout << ans << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

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