Submission #1169775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169775		anmattroi	Towns (IOI15_towns)	C++17	100 / 100	10 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 = 0, nodeB = 0, diameter = 0, condition = 0;

int cached0[maxn], cachedA[maxn];

int cmp(int x, int y) {
    int x_plus_y = getDistance(x, y),
        x_minus_y = cachedA[x] - cachedA[y],
    disX = (x_plus_y + x_minus_y) / 2;

    int a_plus_zero = cachedA[0],
        a_minus_zero = cachedA[x] - cached0[x],
    disA = (a_plus_zero + a_minus_zero) / 2,
    distance_to_mid = cachedA[x] - disA;

    return (disX < distance_to_mid);
}
int solve(int N, vector<int> Mid) {

    int cnt = 0;

    vector<int> Lis, Bucket; //orz fischer
    Lis.emplace_back(Mid[0]);
    for (int i = 1; i < Mid.size(); i++) {
        int u = Mid[i];
        if (cmp(u, Lis.back())) Bucket.emplace_back(u);
        else {
            Lis.emplace_back(u);
            if (!Bucket.empty()) {
                Lis.emplace_back(Bucket.back());
                Bucket.pop_back();
            }
        }
    }
    int candidate = Lis.back();
    while (!Lis.empty()) {
        if (cmp(candidate, Lis.back())) {
            if (Lis.size() >= 2) {
                ++cnt;
                Lis.pop_back(); Lis.pop_back();
            } else {
                Bucket.emplace_back(Lis.back());
                Lis.pop_back();
            }
            continue;
        }
        if (Bucket.empty()) return 0;
        Bucket.pop_back();
        Lis.pop_back();
        ++cnt;
    }
    cnt += Bucket.size();
    return (cnt > (N/2));
}

void unsolve(int N, int disA) {
    int szL = 0, szR = 0;
    vector<int> Mid;
    for (int i = 0; i < N; i++) {
         int A_minus_zero = cachedA[i] - cached0[i],
            A_plus_zero = cachedA[0];
        int dA = (A_minus_zero+A_plus_zero) / 2;
        if (dA < disA) ++szL;
        else if (dA > disA) ++szR;
        else Mid.emplace_back(i);
    }
    if (szL > (N/2) || szR > (N/2)) return;
    if (!solve(N, Mid)) condition = 1;
}

int hubDistance(int N, int sub) {

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

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

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

    diameter = mx;

    int disA = 0;

    vector<int> possibilities;

    for (int i = 1; i < N; i++)
    if (i != nodeA) {
        int A_minus_zero = cachedA[i] - cached0[i],
            A_plus_zero = cachedA[0];
        int dA = (A_minus_zero+A_plus_zero) / 2;
        if (abs(2*dA - (diameter)) < abs(2*disA - (diameter))) {
            disA = dA;
            possibilities.assign(1, disA);
        } else if (abs(2*dA - (diameter)) == abs(2*disA - (diameter))) possibilities.emplace_back(dA);
    }
    sort(possibilities.begin(), possibilities.end());
    possibilities.erase(unique(possibilities.begin(), possibilities.end()), possibilities.end());

    for (int dm : possibilities) unsolve(N, dm);

    int ans = max(disA, diameter - disA);

    return condition ? ans : -ans;
}

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