Submission #494691

#	Time	Username	Problem	Language	Result	Execution time	Memory
494691		thecodingwizard	Towns (IOI15_towns)	C++11	13 / 100	97 ms	1136 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"

using namespace std;

#define ii pair<int, int>
#define mp make_pair

int A, B;
int dA, dB;
map<ii, int> cached;
int ct = 0;
int getD(int a, int b) {
    if (a == b) return 0;
    if (a > b) swap(a, b);
    if (cached.count(mp(a, b))) return cached[mp(a, b)];
    ct++;
    return cached[mp(a, b)] = getDistance(a, b);
}

int isInA(int x) {
    return (getD(x, A) + getD(A, B) - getD(B, x)) / 2 < dA;
}
int isInB(int x) {
    return (getD(x, B) + getD(A, B) - getD(A, x)) / 2 < dB;
}

int getR(int x) {
    if (isInA(x) || isInB(x)) assert(false);
    return (getD(A, x) + getD(B, x) - getD(A, B)) / 2;
}

int hubDistance(int N, int sub) {
    ct = 0;
    cached.clear();
	int maxDist = -1;
    A = -1;
	for (int i = 1; i < N; i++) {
		int d = getD(0, i);
		if (d > maxDist) {
			maxDist = d;
			A = i;
		}
	}
    maxDist = -1;
    B = -1;
	for (int i = 0; i < N; i++) {
		int d = getD(A, i);
		if (d > maxDist) {
			maxDist = d;
			B = i;
		}
	}
    int opt = 1e9;
	for (int i = 0; i < N; i++) {
        int distTo0 = getD(B, i);
        int distTo1 = getD(A, i);
        int dist0 = (maxDist + distTo0 - distTo1)/2;
        int dist1 = (maxDist + distTo1 - distTo0)/2;
        if (max(dist0, dist1) < opt) {
            opt = max(dist0, dist1);
            dA = dist1;
            dB = dist0;
        }
    }

    int mult = 1;
    if (sub == 2 || true) {
        int tot = 0;
        set<int> done;
        for (int i = 0; i < N; i++) {
            int sz = 0;
            if (isInA(i) || isInB(i)) continue;
            if (done.count(i)) continue;
            for (int j = 0; j < N; j++) {
                if (isInA(j) || isInB(j)) continue;
                if (getD(i, j) != getR(i) + getR(j)) {
                    done.insert(j);
                    sz++;
                }
            }
            tot += sz;
            if (sz > N/2) {
                mult = -1;
            }
        }
        int sz = 0;
        for (int i = 0; i < N; i++) {
            if (isInA(i)) {
                sz++;
            }
        }
        tot += sz;
        if (sz > N/2) mult = -1;
        sz = 0;
        for (int i = 0; i < N; i++) {
            if (isInB(i)) sz++;
        }
        tot += sz;
        if (sz > N/2) mult = -1;
        assert(tot == N);
    }
    assert(ct <= N*(N-1)/2);

    return opt*mult;
}

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