oj.uz

Submission #421606

# Submission time Handle Problem Language Result Execution time Memory
421606 2021-06-09T09:58:01 Z Aldas25 Towns (IOI15_towns) C++14
25 / 100
 26 ms 1112 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 16 ms 332 KB Output is correct
2 Correct 14 ms 1112 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 26 ms 924 KB Output is correct
5 Correct 18 ms 944 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 428 KB Output is correct
2 Correct 13 ms 844 KB Output is correct
3 Correct 19 ms 920 KB Output is correct
4 Correct 18 ms 920 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 424 KB Output isn't correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 420 KB Output isn't correct
2 Halted 0 ms 0 KB -