oj.uz

Submission #727167

# Submission time Handle Problem Language Result Execution time Memory
727167 2023-04-20T06:42:04 Z becaido Towns (IOI15_towns) C++17
100 / 100
 18 ms 408 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;

const int N = 111;

int n, A, B, cr;
int dis[N][N];
int d[N], r[N];

inline int D(int a, int b) {
    if (a == b) return 0;
    if (dis[a][b]) return dis[a][b];
    return dis[a][b] = dis[b][a] = getDistance(a, b);
}

inline bool same(int a, int b) {
    if (r[b] != cr) swap(a, b);
    if (r[a] < cr) return r[b] < cr;
    if (r[a] > cr) return r[b] > cr;
    return d[a] + d[b] != D(a, b);
}

int hubDistance(int N, int sub) {
    n = N;
    for (int i = 0; i < n; i++) fill(dis[i], dis[i] + n, 0);
    A = B = 0;
    for (int i = 0; i < n; i++) if (D(0, i) > D(0, A)) A = i;
    for (int i = 0; i < n; i++) if (D(A, i) > D(A, B)) B = i;
    int mn = INT_MAX;
    for (int i = 0; i < n; i++) {
        d[i] = (D(0, i) + D(A, i) - D(0, A)) / 2;
        r[i] = D(A, i) - d[i];
        mn = min(mn, max(r[i], D(A, B) - r[i]));
    }
    vector<int> vc;
    for (int i = 0; i < n; i++) if (max(r[i], D(A, B) - r[i]) == mn) vc.emplace_back(r[i]);
    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end());
    if (vc.size() > 1) {
        int cnt = 0;
        for (int i = 0; i < n; i++) cnt += r[i] <= vc[0];
        if (cnt * 2 <= n) swap(vc[0], vc[1]);
    }
    cr = vc[0];
    vector<pair<int, int>> cur, die;
    for (int i = 0; i < n; i++) cur.emplace_back(i, 1);
    while (cur.size() > 1) {
        vector<pair<int, int>> tmp;
        for (int i = 0; i + 1 < cur.size(); i += 2) {
            if (same(cur[i].first, cur[i + 1].first)) tmp.emplace_back(cur[i].first, cur[i].second + cur[i + 1].second);
            else {
                if (cur[i].second < cur[i + 1].second) swap(cur[i], cur[i + 1]);
                if (cur[i].second == cur[i + 1].second) die.emplace_back(cur[i]), die.emplace_back(cur[i + 1]);
                else tmp.emplace_back(cur[i].first, cur[i].second - cur[i + 1].second), die.emplace_back(cur[i].first, cur[i + 1].second), die.emplace_back(cur[i + 1]);
            }
        }
        if (cur.size() & 1) tmp.emplace_back(cur.back());
        cur = tmp;
    }
    if (cur.size() == 0) return max(cr, D(A, B) - cr);
    int cnt = cur[0].second;
    for (auto [x, c] : die) if (same(cur[0].first, x)) cnt += c;
    return (cnt * 2 <= n ? 1 : -1) * max(cr, D(A, B) - cr);
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:26:21: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   26 | int hubDistance(int N, int sub) {
      |                 ~~~~^
towns.cpp:7:11: note: shadowed declaration is here
    7 | const int N = 111;
      |           ^
towns.cpp:52:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (int i = 0; i + 1 < cur.size(); i += 2) {
      |                         ~~~~~~^~~~~~~~~~~~
towns.cpp:26:28: warning: unused parameter 'sub' [-Wunused-parameter]
   26 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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 400 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 13 ms 340 KB Output is correct
5 Correct 12 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 9 ms 340 KB Output is correct
3 Correct 14 ms 340 KB Output is correct
4 Correct 13 ms 400 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 13 ms 400 KB Output is correct
3 Correct 0 ms 272 KB Output is correct
4 Correct 18 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 12 ms 404 KB Output is correct
3 Correct 17 ms 400 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 408 KB Output is correct
2 Correct 13 ms 404 KB Output is correct
3 Correct 12 ms 340 KB Output is correct