제출 #1157469

#제출 시각아이디문제언어결과실행 시간메모리
1157469Doncho_BonbonchoTowns (IOI15_towns)C++20
100 / 100
20 ms328 KiB
#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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...