# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
640802 | 2022-09-15T09:26:19 Z | piOOE | Towns (IOI15_towns) | C++17 | 15 ms | 360 KB |
#include <bits/stdc++.h> #include "towns.h" using namespace std; int hubDistance(int n, int sub) { vector<int> dist0(n); for (int i = 1; i < n; ++i) { dist0[i] = getDistance(0, i); } int a = max_element(dist0.begin(), dist0.end()) - dist0.begin(); vector<int> dist(n); dist[0] = dist0[a]; for (int i = 1; i < n; ++i) { dist[i] = i == a ? 0 : getDistance(i, a); } int b = max_element(dist.begin(), dist.end()) - dist.begin(); vector<int> pos(n); pos[0] = (dist0[a] - dist0[b] + dist[b]) >> 1; for (int i = 1; i < n; ++i) { pos[i] = min(pos[0], (dist0[a] - dist0[i] + dist[i]) >> 1); } int ans = numeric_limits<int>::max(); map<int, vector<int>> mp; for (int i = 0; i < n; ++i) { ans = min(ans, max(pos[i], dist[b] - pos[i])); mp[pos[i]].push_back(i); } int L = 0, R = n; for (auto [len, adj]: mp) { R -= adj.size(); if (max(len, dist[b] - len) == ans && max(L, R) <= n / 2) { if (adj.size() <= n / 2) { return ans; } vector<int> p(n); int bal = 0, x; for (int y: adj) { if (bal == 0) { x = y; } if (x == y || getDistance(x, y) < dist[x] + dist[y] - 2 * len) { p[y] = x, ++bal; } else { p[y] = y, --bal; } } int last = -1, cnt = 0; for (int y: adj) { if (p[y] == y && getDistance(x, y) < dist[x] + dist[y] - 2 * len) { last = y; } cnt += p[y] == last; } if (cnt <= n / 2) { return ans; } else { return -ans; } } L += adj.size(); } return -ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 340 KB | Output is correct |
2 | Correct | 13 ms | 356 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 13 ms | 308 KB | Output is correct |
5 | Correct | 12 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 352 KB | Output is correct |
2 | Correct | 9 ms | 340 KB | Output is correct |
3 | Correct | 13 ms | 328 KB | Output is correct |
4 | Correct | 13 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 340 KB | Output is correct |
2 | Correct | 13 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 13 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 360 KB | Output is correct |
2 | Correct | 13 ms | 352 KB | Output is correct |
3 | Correct | 14 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 340 KB | Output is correct |
2 | Correct | 14 ms | 348 KB | Output is correct |
3 | Correct | 13 ms | 344 KB | Output is correct |