| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 380281 |
2021-03-20T20:24:37 Z |
idk321 |
Towns (IOI15_towns) |
C++11 |
|
46 ms |
1004 KB |
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, cur;
const int N = 300;
int dist[N][N];
const int M = 1000000000;
vector<int> nodes;
vector<array<int, 2>> adj[N];
void solve()
{
if (nodes.size() == 1) return;
int toDel = -1;
for (int i = 0; i < nodes.size(); i++)
{
for (int j = 0; j < nodes.size(); j++)
{
if (i == j) continue;
bool ok = true;
for (int k = 0; k < nodes.size(); k++)
{
if (k == i || k == j) continue;
if (dist[nodes[k]][nodes[i]] - dist[nodes[k]][nodes[j]] != dist[nodes[i]][nodes[j]])
{
ok = false;
break;
}
}
if (ok)
{
adj[nodes[i]].push_back({nodes[j], dist[nodes[i]][nodes[j]]});
adj[nodes[j]].push_back({nodes[i], dist[nodes[i]][nodes[j]]});
toDel = nodes[i];
break;
}
}
if (toDel != -1) break;
}
if (toDel != -1)
{
for (int i = 0; i < nodes.size(); i++)
{
if (nodes[i] == toDel)
{
nodes.erase(nodes.begin() + i);
break;
}
}
solve();
return;
}
array<int, 2> ar = {-1, -1};
for (int i = 0; i < nodes.size(); i++)
{
for (int j = i + 1; j < nodes.size(); j++)
{
bool ok = true;
int ci = M;
for (int k = 0; k < nodes.size(); k++)
{
if (k == i || k == j) continue;
if (ci == M)
{
ci = dist[nodes[j]][nodes[k]] - dist[nodes[i]][nodes[k]];
} else
{
if (ci != dist[nodes[j]][nodes[k]] - dist[nodes[i]][nodes[k]])
{
ok = false;
break;
}
}
}
if (ok)
{
ar[0] = nodes[i];
ar[1] = nodes[j];
adj[nodes[i]].push_back({cur, (dist[nodes[i]][nodes[j]] - ci) / 2});
adj[cur].push_back({nodes[i], (dist[nodes[i]][nodes[j]] - ci) / 2});
adj[nodes[j]].push_back({cur, (dist[nodes[i]][nodes[j]] + ci) / 2});
for (int l = 0; l < N; l++)
{
if (dist[nodes[i]][l] != 0)
{
dist[cur][l] = dist[nodes[i]][l] - (dist[nodes[i]][nodes[j]] - ci) / 2;
dist[l][cur] = dist[cur][l];
}
}
adj[cur].push_back({nodes[j], (dist[nodes[i]][nodes[j]] + ci) / 2});
nodes.push_back(cur);
cur++;
break;
}
}
if (ar[0] != -1) break;
}
for (int i = 0; i < nodes.size(); i++)
{
if (nodes[i] == ar[0])
{
nodes.erase(nodes.begin() + i);
}
}
for (int i = 0; i < nodes.size(); i++)
{
if (nodes[i] == ar[1])
{
nodes.erase(nodes.begin() + i);
}
}
solve();
}
int getMaxDist(int node, int par)
{
int res = 0;
for (auto next : adj[node])
{
if (next[0] == par) continue;
res = max(res, getMaxDist(next[0], node) + next[1]);
}
return res;
}
int sz[N];
void getSz(int node, int par)
{
sz[node] = 0;
if (adj[node].size() == 1) sz[node] = 1;
for (auto next : adj[node])
{
if (next[0] == par) continue;
getSz(next[0], node);
sz[node] += sz[next[0]];
}
}
bool isGood(int node)
{
for (auto next : adj[node])
{
if (sz[next[0]] > n / 2) return false;
}
return true;
}
int hubDistance(int N, int sub) {
n = N;
cur = n;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
dist[i][j] = getDistance(i, j);
dist[j][i] = dist[i][j];
}
}
for (int i = 0; i < n; i++) nodes.push_back(i);
solve();
bool good = false;
int r = M;
for (int i = n; i < cur; i++)
{
r = min(r, getMaxDist(i, -1));
}
for (int i = n; i < cur; i++)
{
if (getMaxDist(i, -1) == r)
{
getSz(i, -1);
good = good || isGood(i);
}
}
nodes.clear();
for (int i = 0; i < cur; i++) adj[i].clear();
if (!good) r *= -1;
return r;
}
Compilation message
towns.cpp: In function 'void solve()':
towns.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (int i = 0; i < nodes.size(); i++)
| ~~^~~~~~~~~~~~~~
towns.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int j = 0; j < nodes.size(); j++)
| ~~^~~~~~~~~~~~~~
towns.cpp:30:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int k = 0; k < nodes.size(); k++)
| ~~^~~~~~~~~~~~~~
towns.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 0; i < nodes.size(); i++)
| ~~^~~~~~~~~~~~~~
towns.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i = 0; i < nodes.size(); i++)
| ~~^~~~~~~~~~~~~~
towns.cpp:72:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int j = i + 1; j < nodes.size(); j++)
| ~~^~~~~~~~~~~~~~
towns.cpp:76:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int k = 0; k < nodes.size(); k++)
| ~~^~~~~~~~~~~~~~
towns.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int i = 0; i < nodes.size(); i++)
| ~~^~~~~~~~~~~~~~
towns.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int i = 0; i < nodes.size(); i++)
| ~~^~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:182:31: warning: declaration of 'N' shadows a global declaration [-Wshadow]
182 | int hubDistance(int N, int sub) {
| ^
towns.cpp:9:11: note: shadowed declaration is here
9 | const int N = 300;
| ^
towns.cpp:182:28: warning: unused parameter 'sub' [-Wunused-parameter]
182 | int hubDistance(int N, int sub) {
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
748 KB |
Output is correct |
| 2 |
Correct |
26 ms |
620 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
24 ms |
492 KB |
Output is correct |
| 5 |
Correct |
27 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
620 KB |
Output is correct |
| 2 |
Correct |
24 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
25 ms |
1004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
