Submission #338799

#	Time	Username	Problem	Language	Result	Execution time	Memory
338799		notmahi	Towns (IOI15_towns)	C++14	0 / 100	19 ms	1132 KiB

towns

#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;
	int maxDistForB = -1;
	for (int i = 0; i < N; i++) {
		if ((i == cityA) || (distance[i][cityA] != -1)) {
			continue;
		}
		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;
	int maxDistForC = -1;
	for (int i = 0; i < N; i++) {
		if ((i == cityB) || (distance[i][cityB] != -1)) {
			continue;
		}
		distance[i][cityB] = getDistance(cityB, i);
		distance[cityB][i] = distance[i][cityB];
		if(distance[i][cityB] > maxDistForB) {
			cityC = i;
			maxDistForB = 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;
	for (int i = 0; i < N; i++) {
		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;

		R = (R < hubToB) ? hubToB : R;
		R = (R < hubToC) ? hubToC : R;
	}
	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:30:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   30 |    maxDistForB = distance[cityB][cityA];
      |                  ~~~~~~~~~~~~~~~~~~~~~^
towns.cpp:46:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   46 |    maxDistForB = distance[cityB][cityC];
      |                  ~~~~~~~~~~~~~~~~~~~~~^
towns.cpp:71:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   71 |  return R;
      |         ^
towns.cpp:37:6: warning: unused variable 'maxDistForC' [-Wunused-variable]
   37 |  int maxDistForC = -1;
      |      ^~~~~~~~~~~
towns.cpp:3:28: warning: unused parameter 'sub' [-Wunused-parameter]
    3 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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