Submission #20195

#	Time	Username	Problem	Language	Result	Execution time	Memory
20195		suhgyuho_william	Towns (IOI15_towns)	C++98	25 / 100	23 ms	4 KiB

towns

#include "towns.h"
#include <algorithm>
#include <stdio.h>

using namespace std;

int N,R;
int v,big;
int a[150][150];
int x[150],towns[150],tmp[150];
int cnt[150],far[150];
int left[150],right[150];

void getR(){
	int i,j;
	int rear,t;

	for(i=1; i<N; i++) a[0][i] = a[i][0] = getDistance(0,i);
	big = 0;
	for(i=1; i<N; i++){
		if(big < a[0][i]){
			big = a[0][i];
			v = i;
		}
	}
	for(i=1; i<N; i++){
		if(i == v) continue;
		a[v][i] = a[i][v] = getDistance(i,v);
	}
	rear = 0;
	for(i=1; i<N; i++){
		if(i == v) continue;
		x[i] = a[0][i]+a[v][i]-big;
		x[i] /= 2;
		rear++;
		towns[rear] = a[0][i]-x[i];
	}
	sort(towns+1,towns+rear+1);
	t = 0;
	for(i=1; i<=rear; i++){
		if(towns[i] == towns[i-1]) continue;
		t++;
		tmp[t] = towns[i];
	}
	rear = t;
	for(i=1; i<=rear; i++) towns[i] = tmp[i];
	for(i=1; i<=rear; i++) cnt[i] = 0;
	R = 1000000;
    for(i=1; i<=rear; i++){
		far[i] = 0;
		for(j=1; j<N; j++){
			if(j == v) continue;
			if(a[0][j]-x[j] == towns[i]){
				cnt[i]++;
				far[i] = max(far[i],x[j]);
			}
		}
    }
    left[1] = towns[1];
	for(i=2; i<=rear; i++){
		left[i] = max(left[i-1],far[i-1])+(towns[i]-towns[i-1]);
	}
	right[rear] = big-towns[rear];
	for(i=rear-1; i>=1; i--){
		right[i] = max(right[i+1],far[i+1])+(towns[i+1]-towns[i]);
	}
	for(i=1; i<=rear; i++){
		R = min(R,max(far[i],max(left[i],right[i])));
	}
}

int hubDistance(int n, int sub) {
	N = n;
	getR();

	return R;
}

Compilation message (stderr)

towns.cpp:72:28: warning: unused parameter 'sub' [-Wunused-parameter]
 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