oj.uz

Submission #586744

# Submission time Handle Problem Language Result Execution time Memory
586744 2022-06-30T15:47:52 Z InternetPerson10 Towns (IOI15_towns) C++17
35 / 100
 14 ms 368 KB 
#include "towns.h"
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

map<pair<int, int>, int> distances;

int getDist(int i, int j) {
    if(i == j) return 0;
    if(i > j) swap(i, j);
    if(distances.count({i, j})) {
        return distances[make_pair(i, j)];
    }
    return distances[make_pair(i, j)] = getDistance(i, j);
}

vector<int> dists;
map<ll, int> xs;

int hubDistance(int n, int sub) {
    ll ans = 2e10;
    distances.clear();
    dists.clear();
    xs.clear();
    dists.resize(n);
    int ma = -1, best = -1;
    for(int i = 0; i < n; i++) {
        dists[i] = getDist(0, i);
        if(ma < dists[i]) {
            ma = dists[i];
            best = i;
        }
    }
    int x = best;
    ma = -1, best = -1;
    for(int i = 0; i < n; i++) {
        dists[i] = getDist(x, i);
        if(ma < dists[i]) {
            ma = dists[i];
            best = i;
        }
    }
    int y = best;
    ll c = ma;
    for(int i = 0; i < n; i++) {
        int a = getDist(x, i);
        int b = getDist(y, i);
        ans = min(ans, max(a + c - b, b + c - a));
        if(!xs.count(a+c-b)) {
            xs[a+c-b] = 1;
        }
        else xs[a+c-b]++;
    }
    ans /= 2;
    ll cand = -1;
    int sum = 0;
    for(auto p : xs) {
        bool ok = (max(p.first, 2 * c - p.first) == (ll)ans * 2);
        ok &= (sum <= n/2);
        sum += p.second;
        if(sub == 4) ok &= (p.second <= n/2);
        ok &= (n - sum <= n/2);
        if(ok) {
            if(sub == 4) return (int)ans;
        }
    }
    if(sub == 4) {
        return (int)-ans;
    }
    return (int)ans;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:56:8: warning: unused variable 'cand' [-Wunused-variable]
   56 |     ll cand = -1;
      |        ^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 10 ms 368 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 13 ms 356 KB Output is correct
5 Correct 14 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 364 KB Output is correct
2 Correct 11 ms 340 KB Output is correct
3 Correct 13 ms 360 KB Output is correct
4 Correct 13 ms 340 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 360 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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