| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 286437 |
2020-08-30T11:51:58 Z |
AaronNaidu |
Towns (IOI15_towns) |
C++14 |
|
23 ms |
1024 KB |
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;
int n;
int dists[111][111];
int maxDists[1000];
int distToRoot[1000];
int lcaHeights[111][111];
int leafCount[1000];
int par[1000];
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";
par[node] = parent;
int leafC = 0;
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));
leafC += leafCount[i.first];
}
}
if (tree[node].size() == 1)
{
leafC = 1;
}
leafCount[node] = leafC;
//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};
}*/
bool isGood(int node) {
//cout << "Checking " << node << "\n";
int totSum = 0;
for (auto i : tree[node])
{
if (i.first != par[node])
{
if (leafCount[i.first] > n/2)
{
return false;
}
totSum += leafCount[i.first];
}
}
if (n-totSum > n/2)
{
return false;
}
return true;
}
int hubDistance(int N, int sub) {
//secret();
n = N;
pointer = 200;
for (int i = 0; i < 1000; i++)
{
tree[i].clear();
distToRoot[i] = -1;
maxDists[i] = -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++)
{
maxDists[i] = dfs(i, -1, 0, i);
minMax = min(maxDists[i],minMax);
}
bool hasGoodHub = false;
for (int i = 200; i < pointer; i++)
{
if (maxDists[i] == minMax)
{
hasGoodHub |= isGood(i);
}
}
if (hasGoodHub)
{
return minMax;
}
return -minMax;
}
Compilation message
towns.cpp: In function 'void solveRegion(std::vector<int>, int, int)':
towns.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = 1; i < leafs.size(); i++)
| ~~^~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:130:28: warning: unused parameter 'sub' [-Wunused-parameter]
130 | int hubDistance(int N, int sub) {
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
512 KB |
Output is correct |
| 2 |
Correct |
17 ms |
512 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
21 ms |
512 KB |
Output is correct |
| 5 |
Correct |
23 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
512 KB |
Output is correct |
| 2 |
Correct |
22 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
22 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
