oj.uz

답안 #338830

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338830 2020-12-24T04:28:16 Z notmahi 도시들 (IOI15_towns) C++14
25 / 100
 24 ms 1024 KB 
#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

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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 492 KB Output is correct
2 Correct 18 ms 492 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 20 ms 492 KB Output is correct
5 Correct 21 ms 1024 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 492 KB Output is correct
2 Correct 15 ms 492 KB Output is correct
3 Correct 23 ms 492 KB Output is correct
4 Correct 21 ms 1004 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 492 KB Output isn't correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -