Submission #1216040

#TimeUsernameProblemLanguageResultExecution timeMemory
1216040LemserTowns (IOI15_towns)C++20
35 / 100
10 ms328 KiB
#include "towns.h" #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("avx2") #pragma GCC target("popcnt") using namespace std; using ll = long long; using ull = unsigned long long; using lld = long double; using ii = pair<int,int>; using pll = pair<ll, ll>; using vi = vector<int>; using vll = vector<ll>; using vii = vector<ii>; using vpll = vector<pll>; using vlld = vector<lld>; #define all(x) x.begin(),x.end() #define lsb(x) x&(-x) #define gcd(a,b) __gcd(a,b) #define sz(x) (int)x.size() #define mp make_pair #define pb push_back #define fi first #define se second #define fls cout.flush() #define fore(i, l, r) for (auto i = l; i < r; i++) #define fo(i, n) fore (i, 0, n) #define forex(i, r, l) for (auto i = r-1; i >= l; i--) #define ffo(i, n) forex (i, n, 0) bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; } bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; } /* getDistance (i, j) */ int hubDistance(int N, int sub) { int A = 0, B = 0, b = 0; fore (i, 1, N) { int g = getDistance (0, i); if (g > b) { b = g; A = i; } } vector<int> dA(N, 0), dB(N, 0); B = 0; fo (i, N) { if (i == A) continue; int g = getDistance (A, i); dA[i] = g; if (g > b) { b = g; B = i; } } int ans = dA[B], ok = -1; fo (i, N) { if (i == B) continue; dB[i] = getDistance (B, i); } map<ll, ll> cnt; fo (i, N) { if (i == A || i == B) continue; int d = dA[i] + dB[i] - dA[B]; d /= 2; cnt[dA[i] - d]++; ans = min(ans, max(dA[i], dB[i]) - d); } ll sum = 1; for (auto [k, v]: cnt) { if (max(k, dA[B] - k) > ans) { sum += v; continue; } if (v > N/2) { sum += v; continue; } if (sum <= N/2 && N - sum - v <= N/2) ok = 1; sum += v; } if (sub > 2) { return ans * ok; } 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...