Submission #421606

#	Time	Username	Problem	Language	Result	Execution time	Memory
421606		Aldas25	Towns (IOI15_towns)	C++14	25 / 100	26 ms	1112 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define pb push_back
#define f first
#define s second
#define REP(n) FOR(O, 1, (n))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<pii> vii;

const int MAXN = 200;

int n;
int ddd[MAXN][MAXN];

int dist (int a, int b) {
    if (a == b) return 0;

    if (ddd[a][b] == 0) {
        ddd[a][b] = ddd[b][a] = getDistance(a,b);
    }

    return ddd[a][b];
}

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

	FOR(i, 0, n-1) FOR(j, 0, n-1) ddd[i][j] = 0;

	int x = 0, y = 0;
    FOR(i, 1, n-1) if (dist(0, i) > dist(0, x)) x = i;
    FOR(i, 1, n-1) if (dist(x, i) > dist(x, y)) y = i;

    /// x --- y is a diameter

    int ans = 1e9;
    FOR(i, 0, n-1) {
        if (i == x || i == y) continue;
        int d1 = dist(x, i), d2 = dist(y, i);
        int d = (d1 + d2 - dist(x,y)) / 2;
        int a = d1 - d, b = d2 - d;
        if (a == 0 || b == 0) continue;
        int cur = max(a,b);
        ans = min(cur, ans);
    }

	return ans;
}


/*

1 1
11
0 17 18 20 17 12 20 16 23 20 11
17 0 23 25 22 17 25 21 28 25 16
18 23 0 12 21 16 24 20 27 24 17
20 25 12 0 23 18 26 22 29 26 19
17 22 21 23 0 9 21 17 26 23 16
12 17 16 18 9 0 16 12 21 18 11
20 25 24 26 21 16 0 10 29 26 19
16 21 20 22 17 12 10 0 25 22 15
23 28 27 29 26 21 29 25 0 21 22
20 25 24 26 23 18 26 22 21 0 19
11 16 17 19 16 11 19 15 22 19 0
ans: 16



*/

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:32:28: warning: unused parameter 'sub' [-Wunused-parameter]
   32 | 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