Submission #119765

#TimeUsernameProblemLanguageResultExecution timeMemory
119765WhipppedCreamTowns (IOI15_towns)C++17
0 / 100
18 ms512 KiB
#include "towns.h" #include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC target ("sse4") using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; const int maxn = 120; int m, n; int dist0[maxn]; int distu[maxn]; int add[maxn], bran[maxn]; map<int, int> cnt; int hubDistance(int N, int sub) { memset(add, 0, sizeof add); memset(bran, 0, sizeof bran); cnt.clear(); if(sub > 2 && sub != 4) return 0; n = N; int best = 0, dat = -1; for(int i = 1; i< N; i++) { dist0[i] = getDistance(0, i); if(dist0[i]> best) { best = dist0[i]; dat = i; } } int U = dat; best = 0; dat = -1; for(int i = 0; i< N; i++) { if(i == U || i == 0) continue; distu[i] = getDistance(U, i); if(distu[i]> best) { best = distu[i]; dat = i; } } int V = dat; int diam = distu[V]; // printf("(%d->%d) %d\n", U, V, dist[V]); distu[0] = dist0[U]; for(int i = 0; i< N; i++) { if(i == U || i == 0) continue; int br = dist0[i]+distu[i]-dist0[U]; br /= 2; int pos = dist0[i]-br; add[i] = pos; bran[i] = br; cnt[pos]++; } int rad = 1e9; for(auto kk : cnt) { int x = kk.X; // printf("%d: %d\n", x, cnt[x]); if(x< add[V]) continue; rad = min(rad, max(dist0[U]-x, diam-(dist0[U]-x))); } return rad; }
#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...