제출 #41499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41499		RockyB	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	1627 ms	22916 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
 ll maks = 0,mins=1000000010;
 
#define fi first
#define sc second
#define mp make_pair
#define pb push_back
 
vector<pi> pasangan;
vector<ll> dict;
 
ll n;
ll independent = 0;
string a,b;
ll k;
ll x,y;
ll si;
 
ll ternary3(ll x){
	ll ret = 0;
	for(ll i=0;i<si;i++) ret+=labs(pasangan[i].fi-x)+labs(pasangan[i].sc-x);
	return ret;
}
 
ll ternary2(ll x, ll y){
	ll ret =0;
	for(ll i=0;i<si;i++){
		ret+=min(labs(pasangan[i].fi-x)+labs(pasangan[i].sc-x),labs(pasangan[i].fi-y)+labs(pasangan[i].sc-y));
	}
	return ret;
}
 
ll ternary1(ll x){
	ll l = 0,r=dict.size()-1;
	while(l<r){
		if (l+10>=r){
			ll i = l, j = r;
			ll now =LONG_LONG_MAX;
			ll ret;
			for(ll k=i;k<=j;k++){
				ll sek = ternary2(x,dict[k]);
				if (sek<now){
					now=sek;
					ret=k;
				}
			}
			l=r=ret;
		}
 
		ll lt = l+(r-l)/3;
		ll rt = l+(r-l)*2/3;
 
		if (ternary2(x,dict[lt])>ternary2(x,dict[rt])) l=lt;
		else r = rt;
	}
	ll kel = ternary2(x,dict[l]), ker = ternary2(x,dict[r]);
	return min(kel,ker);
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin>>k>>n;
	while(n--){
		cin >> a >> x >> b >> y;
		dict.pb(x); dict.pb(y);
		maks=max(maks,max(x,y));
		mins=min(mins,min(x,y));
		if (a==b) independent += labs(x-y);
		else{
			pasangan.pb(mp(x,y));
		}
	}
 
	sort(dict.begin(),dict.end());
	si = pasangan.size();
	ll l = 0, r = dict.size()-1;
 
	if (k==1){
		while(l<r){
			if (l+10>=r){
				ll i = l, j=r;
				ll now = LONG_LONG_MAX;
				ll ap;
				for (ll k=i;k<=j;k++){
					ll sek = ternary3(dict[k]);
					if (sek<now){
						now=sek;
						ap=k;
					}
				}
				l=r=ap;
			}
			ll lt = l+(r-l)/3;
			ll rt = l+ (r-l)*2/3;
 
			if (ternary3(dict[lt])>ternary3(dict[rt])) l=lt;
			else r=rt;
		}
 
		independent+=si;
		cout << independent+min(ternary3(dict[l]),ternary3(dict[r])) << "\n";
		return 0;
	}
 
	while(l<r){
		if (l+10>=r){
			ll i = l, j=r;
			ll now = LONG_LONG_MAX;
			ll ap;
			for (ll k=i;k<=j;k++){
				ll sek = ternary1(dict[k]);
				if (sek<now){
					now=sek;
					ap=k;
				}
			}
			l=r=ap;
		}
		ll lt = l+(r-l)/3;
		ll rt = l+ (r-l)*2/3;
 
		if (ternary1(dict[lt])>ternary1(dict[rt])) l=lt;
		else r=rt;
	}
 
	independent+=si;
	cout << independent+min(ternary1(dict[l]),ternary1(dict[r])) << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'll ternary1(ll)':
bridge.cpp:54:21: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ll rt = l+(r-l)*2/3;
                     ^
bridge.cpp: In function 'int main()':
bridge.cpp:123:22: warning: 'ap' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ll rt = l+ (r-l)*2/3;
                      ^
bridge.cpp:97:23: warning: 'ap' may be used uninitialized in this function [-Wmaybe-uninitialized]
    ll rt = l+ (r-l)*2/3;
                       ^

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37