Submission #1168923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168923		anmattroi	Towns (IOI15_towns)	C++17	39 / 100	13 ms	328 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define maxn 115
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int nodeA, nodeB, diameter, condition = 0, cachedA[maxn], cachedB[maxn];


bool cmp(int u, int v) {
    int distance_to_mid_point = 0,
        distance_to_lca = 0;

    int A_minus_B = cachedA[u] - cachedB[u],
        A_plus_B = diameter;
    int mid_point_to_A = (A_plus_B + A_minus_B) / 2;
    distance_to_mid_point = cachedA[u] - mid_point_to_A;

    int u_minus_v = cachedA[u] - cachedA[v];
    int u_plus_v = getDistance(u, v);

    distance_to_lca = (u_minus_v + u_plus_v) / 2;

    return (distance_to_lca < distance_to_mid_point);
}

void solve_for_node(int N, int disA, int disB) {
    vector<int> Mid; int SzL = 0, SzR = 0;

    for (int i = 0; i < N; i++) {
        int dA = (diameter + (cachedA[i] - cachedB[i])) / 2;
        if (dA == disA) Mid.emplace_back(i);
        else if (dA < disA) ++SzL;
        else ++SzR;
    }
    int sz = Mid.size();
    int pos = 0;

    for (int i = 1, cnt = 0; i < sz; i++) {
        if (cmp(Mid[i], Mid[pos])) ++cnt;
        else --cnt;
        if (cnt <= 0) {
            cnt = 1;
            pos = i;
        }
    }
    int dem = 0;
    for (int i = 0; i < sz; i++)
        if (cmp(Mid[i], Mid[pos])) ++dem;
    if (dem > (N/2) || SzL > (N/2) || SzR > (N/2)) return;
    condition = 1;
}



int hubDistance(int N, int sub) {
    condition = 0;

    nodeA = 0; nodeB = 0; int mx = -1;

    for (int i = 1; i < N; i++) {
        int t = getDistance(0, i);
        if (mx < t) {
            nodeA = i;
            mx = t;
        }
    }
    mx = -1;
    cachedA[nodeA] = 0;
    for (int i = 0; i < N; i++) {
        int t = cachedA[i] = getDistance(nodeA, i);
        if (i != nodeA && mx < cachedA[i]) {
            mx = cachedA[i];
            nodeB = i;
        }
    }

    int ans = INT_MAX, tong = diameter = mx;

    vector<ii> possible;
    cachedB[nodeB] = 0;
    cachedB[nodeA] = diameter;

    for (int i = 0; i < N; i++)
    if (i != nodeA && i != nodeB) {
        int hieu = cachedA[i] - (cachedB[i] = getDistance(nodeB, i)),
            disA = (tong + (cachedA[i] - cachedB[i])) / 2,
            disB = (tong + (cachedB[i] - cachedA[i])) / 2;

        if (hieu < 0) hieu = -hieu;
        if (ans > (tong+hieu)/2) {
            ans = (tong+hieu)/2;
            possible.clear();
            possible.emplace_back(disA, disB);
        } else if (ans == (tong+hieu)/2) {
            possible.emplace_back(disA, disB);
        }
    }
    sort(possible.begin(), possible.end());
    possible.erase(unique(possible.begin(), possible.end()), possible.end());
    for (auto [u, v] : possible) solve_for_node(N, u, v);

    return condition ? ans : -ans;
}

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