Submission #20196

#	Time	Username	Problem	Language	Result	Execution time	Memory
20196		suhgyuho_william	Towns (IOI15_towns)	C++98	36 / 100	40 ms	2 KiB

towns

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

using namespace std;

int N,R,f;
int v,big;
int a[150][150];
int x[150],towns[150],tmp[150];
int cnt[150],far[150];
int left[150],right[150];
int leftcnt[150],rightcnt[150];
bool hub[150],flag;
int num[150],color[150],colorcnt[150];

void checking(int hubnum){
	int i,j;
	int rear;

	rear = 0;
	for(i=1; i<N; i++){
        if(i == v) continue;
		if(towns[hubnum] == a[0][i]-x[i]){
			rear++;
			num[rear] = i;
		}
	}
	for(i=1; i<=rear; i++) colorcnt[i] = 0;
	for(i=1; i<=rear; i++){
        for(j=1; j<i; j++){
			if(getDistance(num[i],num[j]) != x[num[i]]+x[num[j]]) break;
        }
        if(j == i){
			color[i] = i;
			colorcnt[i]++;
        }else{
			color[i] = color[j];
			colorcnt[color[i]]++;
        }
	}
	flag = true;
	for(i=1; i<=rear; i++){
		if(colorcnt[i] > f) flag = false;
	}
}

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

	f = N/2;
	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];
    leftcnt[1] = 1;
	for(i=2; i<=rear; i++){
		left[i] = max(left[i-1],far[i-1])+(towns[i]-towns[i-1]);
		leftcnt[i] = leftcnt[i-1]+cnt[i-1];
	}
	right[rear] = big-towns[rear];
	rightcnt[rear] = 1;
	for(i=rear-1; i>=1; i--){
		right[i] = max(right[i+1],far[i+1])+(towns[i+1]-towns[i]);
		rightcnt[i] = rightcnt[i+1]+cnt[i+1];
	}
	for(i=1; i<=rear; i++){
		R = min(R,max(far[i],max(left[i],right[i])));
	}
	for(i=1; i<=rear; i++){
		if(R == max(far[i],max(left[i],right[i]))) hub[i] = true;
		else hub[i] = false;
	}
	flag = false;
	for(i=1; i<=rear; i++){
		if(!hub[i]) continue;
		if(cnt[i] <= f && leftcnt[i] <= f && rightcnt[i] <= f){
			flag = true;
		}
	}
	if(flag) return;
	for(i=1; i<=rear; i++){
		if(!hub[i]) continue;
        if(leftcnt[i] <= f && rightcnt[i] <= f && cnt[i] > f){
			checking(i);
        }
	}
	if(!flag) R = -R;
}

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

	return R;
}

Compilation message (stderr)

towns.cpp:130:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub) {
                            ^

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