Submission #1157469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157469		Doncho_Bonboncho	Towns (IOI15_towns)	C++20	100 / 100	20 ms	328 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#include <random>
#include <utility>
using namespace std;

#ifndef LOCAL
#define cerr if(false) cerr
#endif

template<class T, class T2>
inline bool chkmax(T &a, const T2 &b) { return a < b ? a = b, true : false; }

template<class T, class T2>
inline bool chkmin(T &a, const T2 &b) { return a > b ? a = b, true : false; }

typedef long long ll;
const int MAX_N = 128;
const ll inf = 1e18;

int n;
map<pair<int,int>, ll> q;
ll makeQuery(int a, int b) {
    if(a > b) swap(a, b);
    if(a == b) return 0;
    pair<int,int> key = {a, b};
    if(q.find(key) == q.end())
        q[key] = getDistance(a, b);
    return q[key];
}

struct DSU {
    int parent[MAX_N], sz[MAX_N];
    void init() {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }
    int find(int a) {
        return parent[a] == a ? a : parent[a] = find(parent[a]);
    }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return;
        if(sz[a] > sz[b]) swap(a, b);
        parent[a] = b;
        sz[b] += sz[a];
    }
};

int hubDistance(int N, int sub) {
    q.clear();
    n = N;
    vector<ll> to0(n, 0), tor1(n, 0);
    
    for (int i = 1; i < n; i++) {
        to0[i] = makeQuery(0, i);
    }
    
    ll maxd = 0;
    int pos = 0;
    for (int i = 0; i < n; i++) {
        if(chkmax(maxd, to0[i])) {
            pos = i;
        }
    }
    int r1 = pos;
    
    for (int i = 0; i < n; i++) {
        tor1[i] = makeQuery(r1, i);
    }
    
    maxd = 0;
    pos = 0;
    for (int i = 0; i < n; i++) {
        if(chkmax(maxd, tor1[i])) {
            pos = i;
        }
    }
    int r2 = pos;
    
    vector<pair<ll,ll>> vc(n);
    for (int i = 0; i < n; i++) {
        ll dis = (to0[r1] + tor1[i] - to0[i]) / 2;
        vc[i] = {dis, tor1[i] - dis}; // first: hub candidate distance, second: remaining distance
    }
    
    ll ans = maxd;
    for (int i = 0; i < n; i++) {
        ans = min(ans, max(vc[i].first, tor1[r2] - vc[i].first));
    }
    
    vector<ll> want;
    for (int i = 0; i < n; i++) {
        if(ans == max(vc[i].first, tor1[r2] - vc[i].first))
            want.push_back(vc[i].first);
    }
    
    int ok = 0;
    DSU dsu;
    for (auto dis : want) {
        int s = 0, m = 0, l = 0;
        vector<int> now;
        for (int i = 0; i < n; i++) {
            if(vc[i].first < dis)
                s++;
            else if(vc[i].first == dis)
                now.push_back(i);
            else
                l++;
        }
        if(s > n / 2 || l > n / 2) continue;
        
        int nx = now[0], mis = 1, OK = 1;
        dsu.init();
        for (size_t i = 1; i < now.size(); i++) {
            int x = now[i];
            if(nx == 0) {
                mis = 1;
                nx = now[i];
                continue;
            }
            if(makeQuery(nx, x) < vc[nx].second + vc[x].second) {
                dsu.unite(nx, x);
                mis++;
            } else {
                mis--;
            }
            if(mis == 0) nx = 0;
        }
        for (size_t i = 0; i < now.size(); i++) {
            int x = now[i];
            if(x == dsu.find(x)) {
                if(makeQuery(nx, x) < vc[nx].second + vc[x].second)
                    dsu.unite(nx, x);
            }
        }
        for (size_t i = 0; i < now.size(); i++) {
            int x = now[i];
            if(x == dsu.find(x) && dsu.sz[x] > n / 2)
                OK = 0;
        }
        ok |= OK;
    }
    
    return (ok == 1 ? 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