oj.uz

Submission #542720

# Submission time Handle Problem Language Result Execution time Memory
542720 2022-03-27T16:26:57 Z hoanghq2004 Towns (IOI15_towns) C++14
35 / 100
 18 ms 888 KB 
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "towns.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 110;

int d[N][N];
int dS[N], dT[N];

int hubDistance(int n, int sub) {
    int S = 0;
    for (int i = 0; i < n; ++i) dS[i] = getDistance(0, i);
    for (int i = 0; i < n; ++i)
        if (dS[i] > dS[S]) S = i;
    for (int i = 0; i < n; ++i) dS[i] = getDistance(S, i);
    int T = 0;
    for (int i = 0; i < n; ++i)
        if (dS[i] > dS[T]) T = i;
    for (int i = 0; i < n; ++i) dT[i] = getDistance(T, i);
    int R = 1e9;
    int h = 0;
    for (int i = 0; i < n; ++i) {
        int cur = (dS[T] + dS[i] - dT[i]) / 2;
        if (max(cur, dS[T] - cur) < R) {
            R = max(cur, dS[T] - cur);
            h = cur;
        }
    }
    if (sub < 3) return R;
    if (sub == 4) {
        int up = 0, down = 0, mid = 0;
        for (int i = 0; i < n; ++i) {
            int cur = (dS[T] + dS[i] - dT[i]) / 2;
            if (cur < h) ++up;
            if (cur > h) ++down;
            if (cur == h) ++mid;
        }
        if (max({up, down, mid}) <= n / 2) return R;
        return - R;
    }
    return R;
}

Compilation message

towns.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
towns.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 596 KB Output is correct
2 Correct 11 ms 696 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 18 ms 888 KB Output is correct
5 Correct 17 ms 824 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 596 KB Output is correct
2 Correct 12 ms 692 KB Output is correct
3 Correct 14 ms 868 KB Output is correct
4 Correct 15 ms 848 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 412 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 15 ms 628 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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