Submission #1020914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020914		amirhoseinfar1385	Towns (IOI15_towns)	C++17	100 / 100	18 ms	1048 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int n,inf=1e9;
map<pair<int,int>,int>mp;
map<int,int>mpa,tof;
int pors(int u,int v){
	if(u==v){
		return 0;
	}
	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(0,u);
}
 
int hubDistance(int N,int sub) {
	mp.clear();
	tof.clear();
	mpa.clear();
	n=N;
	//sub=sub;
	//cout<<"salam"<<endl;
	pair<int,int>di=getdia();
	int mn=inf;
	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(mpa[fake1]>=fake3){
				tof[fake1]=i;
			}
			mpa[fake1]=max(mpa[fake1],fake3);
			if(fake1<fake2){
				ted1++;
			}else{
				ted2++;
			}
		}
	}
	mpa[0]=0;
	mpa[pors(di.first,di.second)]=0;
	tof[0]=di.first;
	tof[pors(di.first,di.second)]=di.second;
	vector<pair<int,int>>allt;
	vector<int>suf,ps,wsuf,wps;
	int sz=0;
	suf.push_back(0);
	ps.push_back(0);
	allt.push_back(make_pair(0,0));
	for(auto x:mpa){
		allt.push_back(make_pair(x.first,x.second));
		suf.push_back(0);
		ps.push_back(0);
		sz++;
	}
	suf.push_back(0);
	ps.push_back(0);
	suf.push_back(0);
	ps.push_back(0);
	allt.push_back(make_pair(0,0));
	wsuf.resize((int)suf.size());
	wps.resize((int)ps.size());
	for(int i=1;i<=sz;i++){
		ps[i]=max(ps[i-1]-allt[i-1].first+allt[i].first,allt[i].second);
		if(allt[i].second<ps[i]){
			wps[i]=wps[i-1];
		}else{
			wps[i]=tof[allt[i].first];
		}
	}
	for(int i=sz;i>=1;i--){
		suf[i]=max(suf[i+1]-allt[i].first+allt[i+1].first,allt[i].second);
		if(allt[i].second<suf[i]){
			wsuf[i]=wsuf[i+1];
		}else{
			wsuf[i]=tof[allt[i].first];
		}
	}
	ted1=ted2=0;
	for(int i=1;i<=sz;i++){
		if(suf[i]>ps[i]){
			tof[allt[i].first]=wsuf[i];
			mpa[allt[i].first]=suf[i];
		}else{
			tof[allt[i].first]=wps[i];
			mpa[allt[i].first]=ps[i];
		}
	}
	int lena=-1;
	for(auto x:mpa){
		if(x.second==mn){
			allv.push_back(make_pair(x.first,tof[x.first]));
		}else if(x.second<mn){
			lena=x.first;
			allv.clear();
			allv.push_back(make_pair(x.first,tof[x.first]));
		}
		mn=min(mn,x.second);	
	}
	for(int i=0;i<n;i++){
		if(pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second)<=lena*2){
			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(ted2*2>n){
			wh=allv.back().second;
			tol=allv.back().first;
		}
	}
	int cntnow=0,last=di.second,komak=di.first;
	vector<vector<int>>allver,allezaf;
	allver.push_back({di.second,di.first});
	allezaf.push_back({1,-1});
	allver.push_back({});
	allezaf.push_back({});
	for(int i=0;i<n;i++){
		if(i==di.first||i==di.second){
			continue;
		}
		if(allver.back().size()==0){
			int z=pors(komak,i)+pors(di.first,di.second)-pors(i,(komak^di.first^di.second));
			z/=2;
			if(z<tol){
				komak=(di.first^di.second^komak);
				tol=pors(di.first,di.second)-tol;
			}
			allver.back().push_back(i);
			allezaf.back().push_back(1);
			cntnow=1;
			last=i;
			continue;
		}
		int z=(pors(komak,last)+pors(komak,i)-pors(i,last))/2;
		if(z>tol){
			allver.back().push_back(i);
			allezaf.back().push_back(1);
			cntnow++;
			continue;
		}else if(cntnow>0){
			allver.back().push_back(i);
			allezaf.back().push_back(-1);
			cntnow--;
			if(cntnow==0&&i!=n-1){
				allver.push_back({});
				allezaf.push_back({});
			}
			continue;
		}
	}
	int cnt=0;
	for(int i=0;i<(int)allver.size();i++){
		if((int)allver[i].size()==0){
			continue;
		}
		int z=(pors(komak,last)+pors(komak,allver[i][0])-pors(allver[i][0],last))/2;
		if(z>tol){
			for(auto x:allezaf[i]){
				if(x==1){
					cnt++;
				}
			}
		}else{
			for(int j=0;j<(int)allver[i].size();j++){
				if(allezaf[i][j]==-1){
					z=(pors(komak,last)+pors(komak,allver[i][j])-pors(allver[i][j],last))/2;
					if(z>tol){
						cnt++;
					}
				}
			}
		}
	}
	if(cnt*2>n){
		return -mn;
	}
	return mn;
}

Compilation message (stderr)

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

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