Submission #1000609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000609		hippo123	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	348 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

#define pr pair<int, int>
#define ll long long
#define pb push_back
#define f first
#define s second

int main(){
	int nb, n; cin>>nb>>n;
	vector<pr> nlist;

	ll dist1=0; 
	for (int i=0; i<n; i++){
		char s1, num1, s2, num2;
		cin>>s1>>num1>>s2>>num2;
		if(s1==s2) dist1+=abs(num1-num2);
		else{
			if(num1>num2) swap(num1, num2);
			nlist.push_back({num1, num2});
		}
	}
	sort(nlist.begin(), nlist.end());
	//=== two medium to calculate
	n=nlist.size();
	ll dist2=0;
	multiset<int, greater<int>> r1;
	multiset<int> r2;  
	
	for (int i=0; i<n; i++){
		r1.insert(nlist[i].f); r1.insert(nlist[i].s);
	}
	while((int)r1.size()>n){
		r2.insert(*r1.begin()); r1.erase(r1.begin());
	}
	dist2=0;
	for (auto it=r1.begin(); it!=r1.end(); it++){
		dist2+=abs(*it-*r1.begin());
	} 
	for (auto it=r2.begin(); it!=r2.end(); it++){
		dist2+=abs(*it-*r1.begin());
	} 
	
	if(nb==1) {
		cout<<dist2+dist1+n<<endl;
		return 0; 
	}

	multiset<int, greater<int>> lft1;
	multiset<int> lft2;
	ll dist=dist2; 
	
	int mid1=*r1.begin(); int mid2=0;
	
	for (int i=0; i<n-1; i++){
		int mid1new;
		
		int elem1=nlist[i].f; int elem2=nlist[i].s;
		dist-=abs(mid1-elem1)+abs(mid1-elem2); 
		if(r1.find(elem1)!=r1.end() && r1.find(elem2)!=r1.end() ){
			r1.erase(r1.find(elem1)); r1.erase(r1.find(elem2)); 
			r1.insert(*r2.begin()), r2.erase(r2.begin());
			
			mid1new=*r1.begin(); 
			
			dist-=2*(mid1new-mid1);			
		}
		else if(r1.find(elem1)!=r1.end() && r1.find(elem2)!=r2.end()){
			r1.erase(r1.find(elem1)); r2.erase(r2.find(elem2));
			mid1new=*r1.begin();
		}
		else{
			r2.erase(r2.find(elem1)); r2.erase(r2.find(elem2));
			r2.insert(*r1.begin()); r1.erase(r1.begin());
			mid1new=*r1.begin();
		}
		mid1=mid1new; 
		
		//
		int mid2new;
		dist+=abs(mid2-elem1)+abs(mid2-elem2);
		if(elem1>mid2 && elem2>mid2){
			lft2.insert(elem1); lft2.insert(elem2);
			lft1.insert(*lft2.begin()); lft2.erase(lft2.begin());
			mid2new=*lft1.begin(); 
			dist-=2*(mid2new-mid2);
		}
		else if(elem1<=mid2 && elem2>mid2){
			lft1.insert(elem1); lft2.insert(elem2);
		}
		else{
			lft1.insert(elem1); lft1.insert(elem2);
			lft2.insert(*lft1.begin()); lft1.erase(lft1.begin());
			mid2new=*lft1.begin();	
		}
		mid2=mid2new; 
		
		dist2=min(dist2, dist);
	}
	cout<<dist2+dist1+n<<endl;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:89:23: warning: 'mid2new' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |   else if(elem1<=mid2 && elem2>mid2){
      |           ~~~~~~~~~~~~^~~~~~~~~~~~~

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