Submission #1168778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168778		anmattroi	Towns (IOI15_towns)	C++17	26 / 100	41 ms	516 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 cached[maxn][maxn], par[maxn], nodeA, nodeB, diameter, condition = 0;


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(int u, int v) {
    int distance_to_mid_point = 0,
        distance_to_lca = 0;

    int A_minus_B = cached[nodeA][u] - cached[nodeB][u],
        A_plus_B = diameter;
    int mid_point_to_A = (A_plus_B + A_minus_B) / 2;
    distance_to_mid_point = cached[nodeA][u] - mid_point_to_A;

    int u_minus_v = cached[nodeA][u] - cached[nodeA][v];
    int u_plus_v = cached[u][v];

    distance_to_lca = (u_minus_v + u_plus_v) / 2;

    if (distance_to_lca < distance_to_mid_point) union_set(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();
    for (int i = 0; i < sz; i++)
    for (int j = i+1; j < sz; j++) {
        int u = Mid[i], v = Mid[j];
        solve(u, v);
    }

    if (SzL > (N/2) || SzR > (N/2)) return;
    for (int i = 0; i < N; i++) if (-par[i] > (N/2)) return;
    condition = 1;
}



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

    for (int i = 0; i < N; i++)
        for (int j = i+1; j < N; j++) cached[i][j] = cached[j][i] = getDistance(i, j);

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

    for (int i = 1; i < N; i++)
    if (mx < cached[0][i]) {
        nodeA = i;
        mx = cached[0][i];
    }
    mx = -1;
    for (int i = 0; i < N; i++)
    if (i != nodeA && mx < cached[nodeA][i]) {
        mx = cached[nodeA][i];
        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: 0 / 12
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39