Submission #1168779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168779		anmattroi	Towns (IOI15_towns)	C++17	35 / 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 par[maxn], nodeA, nodeB, diameter, condition = 0, cached[maxn][maxn];
int find_set(int v) {
    return par[v] < 0 ? v : par[v] = find_set(par[v]);
}

void union_set(int u, int v) {
    u = find_set(u); v = find_set(v);
    if (u == v) return;
    if (par[u] < par[v]) swap(u, v);
    par[v] += par[u];
    par[u] = v;
}



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 + (cached[nodeA][i] - cached[nodeB][i])) / 2;
        if (dA == disA) Mid.emplace_back(i);
        else if (dA < disA) ++SzL;
        else ++SzR;
    }
    int sz = Mid.size();

    if (SzL > (N/2) || SzR > (N/2) || sz > (N/2)) return;
    condition = 1;
}



int hubDistance(int N, int sub) {
    condition = 0;
    for (int i = 0; i < N; i++) par[i] = -1;


    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;
    for (int i = 0; i < N; i++) {
        int t = (cached[nodeA][i] = cached[i][nodeA] = getDistance(nodeA, i));
        if (i != nodeA && mx < cached[nodeA][i]) {
            mx = cached[nodeA][i];
            nodeB = i;
        }
    }
    for (int i = 0; i < N; i++) cached[nodeB][i] = cached[i][nodeB] = getDistance(nodeB, i);

    int ans = INT_MAX, tong = diameter = mx;

    vector<ii> possible;

    for (int i = 0; i < N; i++)
    if (i != nodeA && i != nodeB) {
        int hieu = cached[nodeA][i] - cached[nodeB][i],
            disA = (tong + (cached[nodeA][i] - cached[nodeB][i])) / 2,
            disB = (tong + (cached[nodeB][i] - cached[nodeA][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);
        }
    }
    for (auto [u, v] : possible) solve_for_node(N, u, v);
    return condition ? ans : -ans;
}

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