Submission #338830

#	Time	Username	Problem	Language	Result	Execution time	Memory
338830		notmahi	Towns (IOI15_towns)	C++14	25 / 100	24 ms	1024 KiB

towns

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

int hubDistance(int N, int sub) {
	// long long R = getDistance(0,1);
	long long distance[111][111];

	// First, get all distance from a = 0
	for (int i = 0; i < 111; i++) {
		for (int j = 0; j < 111; j++) {
			if (i == j) {
				distance[i][j] = 0;
			}
			else {
				distance[i][j] = -1;
			}
		}
	}
	
	int cityA = 0;
	int cityB = -1;
	long long maxDistForB = -1;
	for (int i = 0; i < N; i++) {
		if ((i == cityA))
			continue;
		if (distance[i][cityA] == -1)
			distance[i][cityA] = getDistance(cityA, i);
		distance[cityA][i] = distance[i][cityA];
		if(distance[i][cityA] > maxDistForB) {
			cityB = i;
			maxDistForB = distance[cityB][cityA];
		}
	}
	// Maximum of those distances is the city b
	
	// Now do the same thing, again, starting from city B.
	int cityC = 0;
	long long maxDistForC = -1;
	for (int i = 0; i < N; i++) {
		if (i == cityB)
			continue;
		if (distance[i][cityB] == -1)
			distance[i][cityB] = getDistance(cityB, i);
		distance[cityB][i] = distance[i][cityB];
		if(distance[i][cityB] > maxDistForC) {
			cityC = i;
			maxDistForC = distance[cityB][cityC];
		}
	}
	// As it happens, city C is our maximum distance city, from which
	// we should count R.
	for (int i = 0; i < N; i++) {
		if ((distance[i][cityC] != -1)) {
			continue;
		}
		distance[i][cityC] = getDistance(cityC, i);
		distance[cityC][i] = distance[i][cityC];
	}
	long long graphDiameter = distance[cityB][cityC];

	// Now find the value for R
	long long R = 1<<30;
	for (int i = 0; i < N; i++) {
		if (i == cityB || i == cityC)
			continue;
		long long xToB = distance[i][cityB];
		long long xToC = distance[i][cityC];
		long long hubToB = (xToB + graphDiameter - xToC) / 2;
		long long hubToC = (xToC + graphDiameter - xToB) / 2;

		long long candidate = std::max(hubToC, hubToB);
		R = std::min(R, candidate);
	}
	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:76:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   76 |  return R;
      |         ^
towns.cpp:6:28: warning: unused parameter 'sub' [-Wunused-parameter]
    6 | 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