Submission #1066266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066266		noyancanturk	Towns (IOI15_towns)	C++17	25 / 100	71 ms	24668 KiB

towns

#include "towns.h"

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

#define pb push_back

int n;

int dist[200][200];

const int lim=1e6+100;

int pref[lim],suf[lim];
vector<int>blw[lim];

int query(int i,int j){
	if(i==j)return 0;
	if(j<i)swap(i,j);
	if(!dist[i][j])dist[i][j]=getDistance(i,j);
	return dist[i][j];
}

int hubDistance(int N, int sub) {
	for(int i=0;i<=1000000;i++)blw[i].clear();
	memset(dist,0,sizeof(dist));
	n=N;
	int past=-1,point1=-1;
	for(int i=1;i<n;i++){
		if(past<query(0,i)){
			point1=i;
			past=query(0,i);
		}
	}
	past=-1;
	int point2=-1;
	for(int i=0;i<n;i++){
		if(i==point1)continue;
		if(past<query(point1,i)){
			point2=i;
			past=query(point1,i);
		}
	}
	int legsize=0;
	int dist0=query(0,point1);
	if(point2){
		int dist1=query(0,point1),dist2=query(0,point2);
		int ss=dist1+dist2;
		legsize=(ss-past)/2;
		dist0-=legsize;
	}
	blw[0].pb(point1);
	blw[past].pb(point2);
	for(int i=0;i<n;i++){
		if(i==point1||i==point2)continue;
		int ds0=query(0,i),ds1=query(point1,i);
		int legi=(ds0+ds1-query(0,point1))/2;
		int pure0=ds0-legi,pure1=ds1-legi;
		if(pure0<legsize){
			blw[dist0].pb(i);
		}else{
			blw[pure1].pb(i);
		}
	}
	int ans=past;
	for(int i=0;i<past;i++){
		if(blw[i].size()&&max(i,past-i)<ans){
			ans=max(i,past-i);
		}
	}
	return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:24:28: warning: unused parameter 'sub' [-Wunused-parameter]
   24 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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