oj.uz

Submission #529277

# Submission time Handle Problem Language Result Execution time Memory
529277 2022-02-22T15:49:46 Z Cyanmond Towns (IOI15_towns) C++17
25 / 100
 19 ms 948 KB 
// clangformat off
#include "towns.h"
#include <bits/stdc++.h>

template <typename T> bool setmax(T &v, const T a) {
    if (v < a) {
        v = a;
        return true;
    } else {
        return false;
    }
}

template <typename T> bool setmin(T &v, const T a) {
    if (v > a) {
        v = a;
        return true;
    } else {
        return false;
    }
}

constexpr int max_d = 1000010;

int hubDistance(int N, int sub) {
    if (sub == 1 or sub == 2) {
        std::vector<int> dist;
        auto find_maxdist = [&](const int v, std::vector<int> &d) {
            int max = 0, pos = 0;
            for (int i = 0; i < N; ++i) {
                d[i] = getDistance(v, i);
                if (setmax(max, d[i])) {
                    pos = i;
                }
            }
            return std::make_pair(pos, max);
        };

        std::vector<int> memo(N);
        const auto [p1, v1] = find_maxdist(0, memo);
        const auto [p2, diameter] = find_maxdist(p1, memo);

        int res = max_d;
        for (int i = 0; i < N; ++i) {
            if (i == p1 or i == p2) continue;
            const int d1 = memo[i], d2 = getDistance(p2, i);
            const int r = ((d1 + d2) - diameter) / 2;
            setmin(res, std::max(d1 - r, d2 - r));
        }

        return res;
    } else {
        return 0;
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 336 KB Output is correct
2 Correct 9 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 14 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct
2 Correct 11 ms 684 KB Output is correct
3 Correct 19 ms 948 KB Output is correct
4 Correct 15 ms 808 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 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 12 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 336 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 336 KB Output isn't correct
2 Halted 0 ms 0 KB -