제출 #831157

#제출 시각아이디문제언어결과실행 시간메모리
831157skittles1412도시들 (IOI15_towns)C++17
35 / 100
16 ms596 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)) struct DSU { vector<int> p; DSU(int n) : p(n, -1) {} int find(int u) { return p[u] < 0 ? u : (p[u] = find(p[u])); } int size(int u) { return -p[find(u)]; } bool merge(int u, int v) { u = find(u); v = find(v); if (u == v) { return false; } if (p[u] < p[v]) { swap(u, v); } p[v] += p[u]; p[u] = v; return true; } }; int getDistance(int i, int j); struct G { map<pair<int, int>, int> cache; int query(int u, int v) { if (u == v) { return 0; } 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])); } vector<int> cands; { 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; } if (max(cl, cr) <= n / 2) { cands.push_back(k); } cl += v; } if (ok) { return ans; } } if (!sz(cands)) { return -ans; } assert(sz(cands) == 1); if (tc_id > 2 && tc_id != 4) { int u = cands[0]; vector<int> nodes; for (int i = 0; i < n; i++) { if (u_hori[i] == u) { nodes.push_back(i); } } DSU dsu(n); for (auto& a : nodes) { for (auto& b : nodes) { if (G.query(a, b) != u_down[a] + u_down[b]) { dsu.merge(a, b); } } } for (int i = 0; i < n; i++) { dbg(dsu.find(i)); if (dsu.find(i) > n / 2) { return -ans; } } return 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...