Submission #1019115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019115		amirhoseinfar1385	Towns (IOI15_towns)	C++17	0 / 100	10 ms	860 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int n,inf=1e9;
map<pair<int,int>,int>mp;
int pors(int u,int v){
	if(u>v){
		swap(u,v);
	}
	if(mp.count(make_pair(u,v))==0){
		mp[make_pair(u,v)]=getDistance(u,v);
	}
	return mp[make_pair(u,v)];
}
 
pair<int,int>getdia(){
	vector<pair<int,int>>allv;
	for(int i=1;i<n;i++){
		allv.push_back(make_pair(pors(0,i),i));
	}
	sort(allv.begin(),allv.end());
	int u=allv.back().second;
	return make_pair(u,0);
}
 
int hubDistance(int N,int sub) {
	mp.clear();
	n=N;
	//sub=sub;
	//cout<<"salam"<<endl;
	pair<int,int>di=getdia();
	int mn=pors(di.first,di.second);
	int ted1=0,ted2=0;
	vector<pair<int,int>>allv;
	for(int i=0;i<n;i++){
		if(i!=di.first&&i!=di.second){
			int fake1=pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second),fake2=pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first),fake3=pors(i,di.first)+pors(i,di.second)-pors(di.first,di.second);
			fake1/=2;
			fake2/=2;
			fake3/=2;
			if(max(fake1,max(fake2,fake3))==mn){
				allv.push_back(make_pair(fake1,i));
			}else if(max(fake1,max(fake2,fake3))<mn){
				allv.clear();
				allv.push_back(make_pair(fake1,i));
			}
			mn=min(mn,max(fake1,max(fake2,fake3)));
			if(fake1<fake2){
				ted1++;
			}else{
				ted2++;
			}
		}
	}
	sort(allv.begin(),allv.end());
	int wh=allv[0].second,tol=allv[0].first;
	if(allv[0].first!=allv.back().first){
		if(max(ted1,ted2)*2<=n){
			return mn;
		}else if(ted2*2>n){
			wh=allv.back().second;
			tol=allv.back().first;
		}
	}
	int cntnow=0,last=di.second,komak=di.first;
	for(int i=0;i<n;i++){
		if(i==di.first||i==di.second){
			continue;
		}
		int z=(pors(komak,last)+pors(komak,i)-pors(i,last))/2;
		if(z>tol){
			cntnow++;
			continue;
		}else if(cntnow>0){
			cntnow--;
			continue;
		}
		cntnow++;
		last=i;
		if(z!=tol){
			komak=(di.first^di.second^komak);
			tol=pors(di.first,di.second)-tol;
		}
	}
	int cnt=1;
	for(int i=0;i<n;i++){
		if(i==last||i==komak){
			continue;
		}
		if((pors(last,komak)+pors(komak,i)-pors(last,i))/2>tol){
			cnt++;
		}
	}
	if(cnt*2>n){
		return -mn;
	}
	return mn;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:56:6: warning: variable 'wh' set but not used [-Wunused-but-set-variable]
   56 |  int wh=allv[0].second,tol=allv[0].first;
      |      ^~
towns.cpp:26:27: warning: unused parameter 'sub' [-Wunused-parameter]
   26 | int hubDistance(int N,int sub) {
      |                       ~~~~^~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39