| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 286429 | AaronNaidu | 도시들 (IOI15_towns) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;
int n;
int dists[111][111];
int fullDists[1000][1000];
int distToRoot[1000];
int lcaHeights[111][111];
vector<pair<int, int> > tree[1000];
int pointer;
vector<vector<int> > secretDistances;
/*int getDistance(int i, int j) {
return secretDistances[i][j];
}*/
void solveRegion(vector<int> leafs, int root, int rootHeight) {
if (leafs.size() == 0)
{
return;
}
if (leafs.size() == 1)
{
int height = distToRoot[leafs[0]] - rootHeight;
tree[root].push_back({leafs[0], height});
tree[leafs[0]].push_back({root, height});
return;
}
vector<int> part1, part2;
int newRoot = pointer;
pointer++;
int newRootHeight = 1000000007;
int firstInSet = leafs[0];
part1.push_back(firstInSet);
for (int i = 1; i < leafs.size(); i++)
{
if (lcaHeights[firstInSet][leafs[i]] > rootHeight)
{
newRootHeight = min(newRootHeight, lcaHeights[firstInSet][leafs[i]]);
part1.push_back(leafs[i]);
}
else
{
part2.push_back(leafs[i]);
}
}
if (newRootHeight == 1000000007)
{
newRootHeight = rootHeight;
newRoot = root;
pointer--;
}
if (part1.size() > 1)
{
int newHeight = newRootHeight - rootHeight;
tree[root].push_back({newRoot, newHeight});
tree[newRoot].push_back({root, newHeight});
}
solveRegion(part1, newRoot, newRootHeight);
solveRegion(part2, root, rootHeight);
}
int dfs(int node, int parent, int distance, int root) {
//cout << "DFS on node " << node << "\n";
int maxDist = distance;
fullDists[root][node] = distance;
for (auto i : tree[node])
{
if (i.first != parent)
{
//cout << "Spot " << i.first << " distance " << i.second << "away\n";
maxDist = max(maxDist, dfs(i.first, node, distance + i.second, root));
}
}
//cout << "Exit DFS on node " << node << "\n";
return maxDist;
}
/*void secret() {
secretDistances.resize(11);
for (int i = 0; i < 11; i++)
{
secretDistances[i].resize(11);
}
secretDistances[0] = {0, 17, 18, 20, 17, 12, 20, 16, 23, 20, 11};
secretDistances[1] = {17, 0, 23, 25, 22, 17, 25, 21, 28, 25, 16};
secretDistances[2] = {18, 23, 0, 12, 21, 16, 24, 20, 27, 24, 17};
secretDistances[3] = {20, 25, 12, 0, 23, 18, 26, 22, 29, 26, 19};
secretDistances[4] = {17, 22, 21, 23, 0, 9, 21, 17, 26, 23, 16};
secretDistances[5] = {12, 17, 16, 18, 9, 0, 16, 12, 21, 18, 11};
secretDistances[6] = {20, 25, 24, 26, 21, 16, 0, 10, 29, 26, 19};
secretDistances[7] = {16, 21, 20, 22, 17, 12, 10, 0, 25, 22, 15};
secretDistances[8] = {23, 28, 27, 29, 26, 21, 29, 25, 0, 21, 22};
secretDistances[9] = {20, 25, 24, 26, 23, 18, 26, 22, 21, 0, 19};
secretDistances[10] = {11, 16, 17, 19, 16, 11, 19, 15, 22, 19, 0};
}*/
int hubDistance(int N, int sub) {
//secret();
n = N;
pointer = 200;
for (int i = 0; i < 1000; i++)
{
tree[i].clear();
distToRoot[i] = -1;
for (int i = 0; i < 1000; i++)
{
fullDists[i][j] = -1;
}
}
for (int i = 1; i < n; i++)
{
for (int j = i+1; j < n; j++)
{
dists[i][j] = getDistance(i, j);
dists[j][i] = dists[i][j];
}
}
for (int i = 1; i < n; i++)
{
distToRoot[i] = getDistance(i, 0);
}
int minHeight = 1000000007;
for (int i = 1; i < n; i++)
{
for (int j = i+1; j < n; j++)
{
lcaHeights[i][j] = (distToRoot[i] + distToRoot[j] - dists[i][j])/2;
lcaHeights[j][i] = lcaHeights[i][j];
minHeight = min(minHeight, lcaHeights[i][j]);
}
}
tree[0].push_back({pointer, minHeight});
tree[pointer].push_back({0, minHeight});
pointer++;
vector<int> s;
for (int i = 1; i < n; i++)
{
s.push_back(i);
}
solveRegion(s, pointer-1, minHeight);
int minMax = 1000000007;
for (int i = 200; i < pointer; i++)
{
minMax = min(dfs(i, -1, 0, i),minMax);
}
return minMax;
}