oj.uz

Submission #234997

# Submission time Handle Problem Language Result Execution time Memory
234997 2020-05-26T15:29:20 Z dolphingarlic Towns (IOI15_towns) C++14
100 / 100
 24 ms 512 KB 
#include "towns.h"

#include <vector>

inline int max(int X, int Y) { return (X > Y ? X : Y); }

struct Hub {
    int dist_A, R;

    Hub(int A = 1000001, int B = 1000001) {
        dist_A = A;
        R = max(A, B);
    }
} hubs[2];

int hubDistance(int N, int sub) {
    int to_0[110], A, to_A[110], B;
    for (int i = 0, best_A = 0; i < N; i++) {
        to_0[i] = getDistance(0, i);
        if (to_0[i] > best_A) A = i, best_A = to_0[i];
    }
    for (int i = 0, best_B = 0; i < N; i++) {
        to_A[i] = getDistance(A, i);
        if (to_A[i] > best_B) B = i, best_B = to_A[i];
    }

    int hub_cnt = 0;
    for (int i = 0; i < N; i++) {
        int lca_to_A = (to_A[i] + to_A[0] - to_0[i]) / 2;
        Hub potential_hub(lca_to_A, to_A[B] - lca_to_A);

        if (!hub_cnt || potential_hub.R < hubs[0].R) {
            hub_cnt = 1;
            hubs[0] = potential_hub;
        } else if (potential_hub.R == hubs[0].R &&
                   potential_hub.dist_A != hubs[0].dist_A) {
            hub_cnt = 2;
            hubs[1] = potential_hub;
        }
    }

    int is_balanced = -1;
    for (int h = 0; h < hub_cnt; h++) {
        std::vector<int> middle, stck, bckt;
        int closer_to_A = 0, closer_to_0 = 0;
        for (int i = 0; i < N; i++) {
            int lca_to_A = (to_A[i] + to_A[0] - to_0[i]) / 2;

            if (lca_to_A == hubs[h].dist_A) middle.push_back(i);
            else if (lca_to_A < hubs[h].dist_A) closer_to_A++;
            else closer_to_0++;
        }
        if (max(closer_to_A, closer_to_0) > N / 2) continue;
        if (middle.size() <= N / 2) {
            is_balanced = 1;
            break;
        }

        for (int i : middle) {
            if (!stck.size()) {
                stck.push_back(i);
                continue;
            }
            int lca_to_A = (to_A[i] + to_A[stck.back()] - getDistance(i, stck.back())) / 2;
            if (lca_to_A == hubs[h].dist_A) {
                stck.push_back(i);
                if (bckt.size()) {
                    stck.push_back(bckt.back());
                    bckt.pop_back();
                }
            } else bckt.push_back(i);
        }

        int T = stck.back();
        while (stck.size()) {
            int lca_to_A = (to_A[T] + to_A[stck.back()] - getDistance(T, stck.back())) / 2;
            if (lca_to_A == hubs[h].dist_A) {
                stck.pop_back();
                if (bckt.size()) bckt.pop_back();
                else break;
            } else {
                stck.pop_back();
                if (stck.size()) stck.pop_back();
                else bckt.push_back(0);
            }
        }

        if (bckt.size() > N - middle.size()) continue;
        is_balanced = 1;
    }

    return hubs[0].R * is_balanced;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:54:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (middle.size() <= N / 2) {
             ~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:16:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~
towns.cpp:30:43: warning: 'B' may be used uninitialized in this function [-Wmaybe-uninitialized]
         Hub potential_hub(lca_to_A, to_A[B] - lca_to_A);
                                     ~~~~~~^
towns.cpp:23:30: warning: 'A' may be used uninitialized in this function [-Wmaybe-uninitialized]
         to_A[i] = getDistance(A, i);
                   ~~~~~~~~~~~^~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 384 KB Output is correct
2 Correct 19 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 24 ms 384 KB Output is correct
5 Correct 24 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 440 KB Output is correct
2 Correct 21 ms 360 KB Output is correct
3 Correct 24 ms 384 KB Output is correct
4 Correct 24 ms 384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 384 KB Output is correct
2 Correct 23 ms 384 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 23 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 512 KB Output is correct
2 Correct 24 ms 384 KB Output is correct
3 Correct 23 ms 384 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 384 KB Output is correct
2 Correct 24 ms 384 KB Output is correct
3 Correct 24 ms 384 KB Output is correct