Submission #1169691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169691		anmattroi	Towns (IOI15_towns)	C++17	23 / 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;

int cached0[maxn], cachedA[maxn];

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

    int A_minus_B = cachedA[u] - cached0[u],
        A_plus_B = cachedA[0];
    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);
}

int solve(int N, vector<int> Mid) {
    int pos = 0;
    for (int i = 1, cnt = 1; i < Mid.size(); i++) {
        if (cmp(Mid[pos], Mid[i])) ++cnt;
        else --cnt;
        if (cnt == 0) {
            pos = i;
            cnt = 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < Mid.size(); i++)
        ans += cmp(Mid[i], Mid[pos]);
    return (ans > (N/2));
}

int hubDistance(int N, int sub) {

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

    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;


    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;
    }


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

    int szL = 1, szR = 1;
    vector<int> Mid;
    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 (dA < disA) ++szL;
        else if (dA > disA) ++szR;
        else Mid.emplace_back(i);
    }
    if (szL > (N/2) || szR > (N/2)) return -ans;
    return solve(N, Mid) ? -ans : ans;
}

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