Submission #1248520

#TimeUsernameProblemLanguageResultExecution timeMemory
1248520lrnnz도시들 (IOI15_towns)C++20
25 / 100
10 ms484 KiB
#include <bits/stdc++.h> #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <iomanip> #include <queue> #include <random> #include "towns.h" using namespace std; #define all(a) (a).begin(), (a).end() #define ll long long #define ld long double #define ui uint64_t #define cont(set, element) ((set).find(element) != (set).end()) #define pb push_back #define chmin(x, y) (x = min(x, y)) #define chmax(x, y) (x = max(x, y)) /********* DEBUG *********/ template <typename T> void outvec(const vector<T>& Z){ for (const T& x : Z) cout << x << ' '; cout << "\n"; } void printVariable(const any& var) { if (!var.has_value()) { cout << "null"; return; } if (var.type() == typeid(int)) { cout << any_cast<int>(var); } else if (var.type() == typeid(double)) { cout << any_cast<double>(var); } else if (var.type() == typeid(float)) { cout << any_cast<float>(var); } else if (var.type() == typeid(char)) { cout << any_cast<char>(var); } else if (var.type() == typeid(bool)) { cout << (any_cast<bool>(var) ? "true" : "false"); } else if (var.type() == typeid(string)) { cout << any_cast<string>(var); } else if (var.type() == typeid(const char*)) { cout << any_cast<const char*>(var); } else if (var.type() == typeid(long long)) { cout << any_cast<long long>(var); } else { cout << "[unknown type]"; } } template<typename... Args> void outval(Args... args) { vector<any> variables = {args...}; for (size_t i = 0; i < variables.size(); ++i) { printVariable(variables[i]); if (i != variables.size() - 1) { cout << " "; } } cout << "\n"; } #define sp << " " << #define fi first #define se second /********* DEBUG *********/ const ll MOD2 = 1e9 + 7; const ll MOD = 998244353; const ll inf = 1e18; map<pair<ll,ll>, ll> memo; int query(int a, int b){ if (b > a) swap(a,b); if (memo.count({a, b})) return memo[{a,b}]; return memo[{a,b}] = getDistance(a,b); } int hubDistance(int N, int sub) { memo.clear(); int f = 0, hi = 0; for (int i = 1; i < N; i++){ ll x = query(0, i); if (x > hi){ hi = x; f = i; } } int s = 0; hi = 0; for (int i = 0; i < N; i++){ if (i == f) continue; ll x = query(f, i); if (x > hi){ hi = x; s = i; } } auto work = [&](ll a, ll b, ll c) -> ll { ll ab = query(a,b); ll bc = query(b,c); ll ca = query(c,a); ll abc = (ab+bc+ca)/2; a = abc-bc, b = abc-ca, c = abc-ab; return max({a,b,c}); }; ll ans = inf; for (int i = 0; i < N; i++){ chmin(ans, work(f,s,i)); } 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...