제출 #831152

#제출 시각아이디문제언어결과실행 시간메모리
831152skittles1412도시들 (IOI15_towns)C++17
35 / 100
14 ms1064 KiB
#include "bits/extc++.h" using namespace std; template <typename T, typename... U> void dbgh(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; } #ifdef DEBUG #define dbg(...) \ cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \ dbgh(__VA_ARGS__) #else #define dbg(...) #define cerr \ if (false) \ cerr #endif #define endl "\n" #define long int64_t #define sz(x) int(std::size(x)) int getDistance(int i, int j); struct G { map<pair<int, int>, int> cache; int query(int u, int v) { if (u > v) { swap(u, v); } auto [it, inserted] = cache.insert({{u, v}, -1}); if (!inserted) { return it->second; } return it->second = getDistance(u, v); } } G; int hubDistance(int n, int tc_id) { G = {}; auto farthest = [&](int u) -> int { pair<int, int> ans {-1, 0}; for (int i = 0; i < n; i++) { ans = max(ans, {G.query(u, i), i}); } return ans.second; }; int u1 = farthest(0), u2 = farthest(u1), diam = G.query(u1, u2); int u_hori[n], u_down[n]; for (int i = 0; i < n; i++) { int d1 = G.query(u1, i), d2 = G.query(u2, i); u_down[i] = (d1 + d2 - diam) / 2; u_hori[i] = d1 - u_down[i]; } int ans = 1e9; for (int i = 0; i < n; i++) { ans = min(ans, max(u_hori[i], diam - u_hori[i])); } if (tc_id == 4) { map<int, int> mp; for (auto& a : u_hori) { mp[a]++; } bool ok = false; int cl = 0; for (auto& [k, v] : mp) { if (max(k, diam - k) > ans) { cl += v; continue; } int cm = v, cr = n - cl - cm; dbg(cl, cm, cr); if (max({cl, cm, cr}) <= n / 2) { ok = true; } cl += v; } if (!ok) { ans = -ans; } } return 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...