Submission #368415

#	Time	Username	Problem	Language	Result	Execution time	Memory
368415		KoD	Towns (IOI15_towns)	C++17	25 / 100	24 ms	1152 KiB

towns

#include "towns.h"

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>

#define whole(c) std::begin(c), std::end(c)

template <class T>
using Vec = std::vector<T>;

int hubDistance(int N, int sub) {
    Vec<int> from0(N);
    for (int i = 0; i < N; ++i) {
        from0[i] = getDistance(0, i);
    }
    const auto X = std::max_element(whole(from0)) - std::begin(from0);
    Vec<int> fromX(N);
    for (int i = 0; i < N; ++i) {
        fromX[i] = getDistance(X, i);
    }
    const auto Y = std::max_element(whole(fromX)) - std::begin(fromX);
    int ret = 1000005;
    for (int i = 0; i < N; ++i) {
        const auto x = fromX[i];
        const auto y = getDistance(Y, i);
        const auto z = ((x + y) - fromX[Y]) / 2;
        ret = std::min(ret, std::max(x - z, y - z));
    }
    return ret;
}

#ifdef LOCAL

int dist[100][100];

int getDistance(int i, int j) {
    return dist[i][j];
}

int main() {
    int sub, tests;
    std::cin >> sub >> tests;
    while (tests--) {
        int N;
        std::cin >> N;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                std::cin >> dist[i][j];
            }
        }
        std::cout << hubDistance(N, sub) << '\n';
    }
    return 0;
}

#endif

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:21:32: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   21 |         fromX[i] = getDistance(X, i);
      |                                ^
towns.cpp:27:36: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   27 |         const auto y = getDistance(Y, i);
      |                                    ^
towns.cpp:13:28: warning: unused parameter 'sub' [-Wunused-parameter]
   13 | 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