제출 #387343

#제출 시각아이디문제언어결과실행 시간메모리
387343Keshi도시들 (IOI15_towns)C++17
48 / 100
23 ms1004 KiB
//In the name of God #include <bits/stdc++.h> #include "towns.h" using namespace std; typedef int ll; typedef pair<ll, ll> pll; const ll maxn = 200; const ll mod = 1e9 + 7; const ll inf = 1e9; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); #define pb push_back #define Mp make_pair #define F first #define S second #define Sz(x) ll((x).size()) #define all(x) (x).begin(), (x).end() int d[3][maxn], dis[maxn], sz[maxn], h[maxn]; int dist[maxn][maxn]; pll p[maxn]; vector<ll> vec[maxn]; int solve3(int n){ for(ll i = 0; i < n; i++){ for(ll j = i + 1; j < n; j++){ dist[i][j] = dist[j][i] = getDistance(i, j); } } ll v = 0; for(ll i = 1; i < n; i++){ d[0][i] = dist[0][i]; if(d[0][i] > d[0][v]) v = i; } ll u = 0; for(ll i = 0; i < n; i++){ d[1][i] = dist[v][i]; if(d[1][i] > d[1][u]) u = i; } for(ll i = 0; i < n; i++){ d[2][i] = dist[u][i]; } ll D = d[1][u]; map<ll, ll> mp; ll t = 1; for(ll i = 0; i < n; i++){ h[i] = (d[1][i] + d[2][i] - D) / 2; if(!mp[d[1][i] - h[i]]){ mp[d[1][i] - h[i]] = t; dis[t] = d[1][i] - h[i]; vec[t].clear(); t++; } vec[mp[d[1][i] - h[i]]].pb(i); } ll R = inf; for(ll i = 1; i < t; i++){ R = min(R, max(dis[i], D - dis[i])); sz[i] = Sz(vec[i]); p[i] = Mp(dis[i], i); } sort(p + 1, p + t); bool f = 0; ll ssz = 0; for(ll i = 1; i < t; i++){ ll j = p[i].S; if(R == max(p[i].F, D - p[i].F)){ if(ssz > n / 2 || (n - sz[j] - ssz > n / 2)) continue; bool ff = 1; for(ll v1 : vec[j]){ ll e = 0; for(ll v2 : vec[j]){ if(dist[v1][v2] != h[v1] + h[v2]) e++; } if(e > n / 2) ff = 0; } if(ff) f = 1; } ssz += sz[j]; } if(!f) R *= -1; return R; } int solve4(int n){ ll v = 0; for(ll i = 1; i < n; i++){ d[0][i] = getDistance(0, i); if(d[0][i] > d[0][v]) v = i; } ll u = 0; for(ll i = 0; i < n; i++){ d[1][i] = getDistance(v, i); if(d[1][i] > d[1][u]) u = i; } for(ll i = 0; i < n; i++){ d[2][i] = getDistance(u, i); } ll D = d[1][u]; map<ll, ll> mp; ll t = 1; for(ll i = 0; i < n; i++){ h[i] = (d[1][i] + d[2][i] - D) / 2; if(!mp[d[1][i] - h[i]]){ mp[d[1][i] - h[i]] = t; dis[t] = d[1][i] - h[i]; sz[t] = 0; t++; } sz[mp[d[1][i] - h[i]]]++; } ll R = inf; for(ll i = 1; i < t; i++){ R = min(R, max(dis[i], D - dis[i])); p[i] = Mp(dis[i], sz[i]); } sort(p + 1, p + t); bool f = 0; ll ssz = 0; for(ll i = 1; i < t; i++){ if(R == max(p[i].F, D - p[i].F)){ if(p[i].S <= n / 2 && ssz <= n / 2 && (n - p[i].S - ssz) <= n / 2) f = 1; } ssz += p[i].S; } if(!f) R *= -1; return R; } int hubDistance(int n, int sub){ if(sub == 3) return solve3(n); return solve4(n); } /*int main(){ fast_io; return 0; }*/
#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...