제출 #234974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234974		dolphingarlic	도시들 (IOI15_towns)	C++14	25 / 100	28 ms	1152 KiB

towns

#include "towns.h"

#include <iostream>

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

struct Hub {
    int dist_A, dist_B, dist_0, R;

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

int hubDistance(int N, int sub) {
    int to_0[110]{0}, A, to_A[110], B;
    for (int i = 1, 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];
    }
    to_A[0] = to_0[A];
    to_A[A] = 0;
    for (int i = 0, best_B = 0; i < N; i++) {
        if (i == A) continue;
        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++) {
        int closer_to_A = 0, middle = 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;
            int lca_to_0 = (to_0[i] + to_0[A] - to_A[i]) / 2;

            if (lca_to_A < hubs[h].dist_A)
                closer_to_A++;
            else if (lca_to_A == hubs[h].dist_A)
                middle++;
            else
                closer_to_0++;
        }
        std::cerr << closer_to_A << ' ' << middle << ' ' << closer_to_0 << '\n';
        if (max(closer_to_A, closer_to_0) > N / 2) continue;
        // Do other stuff
        is_balanced = 1;
    }

    return hubs[0].R * is_balanced;
}

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:50:17: warning: unused variable 'lca_to_0' [-Wunused-variable]
             int lca_to_0 = (to_0[i] + to_0[A] - to_A[i]) / 2;
                 ^~~~~~~~
towns.cpp:16:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~
towns.cpp:22:21: warning: 'A' may be used uninitialized in this function [-Wmaybe-uninitialized]
     to_A[0] = to_0[A];
               ~~~~~~^
towns.cpp:33:43: warning: 'B' may be used uninitialized in this function [-Wmaybe-uninitialized]
         Hub potential_hub(lca_to_A, to_A[B] - lca_to_A);
                                     ~~~~~~^

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39