| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 432134 |
2021-06-17T21:37:05 Z |
arayi |
Towns (IOI15_towns) |
C++17 |
|
26 ms |
936 KB |
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 150;
int n;
int d[N][N];
int col[N];
bool stg(int l, int a, int b)
{
memset(col, 0, sizeof(col));
int sm1, sm2;
sm1=sm2=0;
for (int i = 0; i < n; i++)
{
int c = (d[a][i] + d[a][b] - d[i][b]) / 2;
if(c < l) sm1++;
else if(c == l) col[i] = 1;
else sm2++;
}
if(sm1 > n/2 || sm2 > n/2) return 0;
for (int i = 0; i < n; i++)
{
if(!col[i]) continue;
for (int j = i + 1; j < n; j++)
{
if(!col[j]) continue;
int c = (d[a][i] + d[a][j] - d[i][j]) / 2;
if(c > l) col[i]++, col[j]++;
}
}
for (int i = 0; i < n; i++) if(col[i] > n/2) return 0;
return 1;
}
int hubDistance(int N, int sub)
{
n = N;
if(sub == 3)
{
int a, b;
a = b = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
{
d[i][j] = d[j][i] = getDistance(i, j);
if(d[i][j] > d[a][b]) a = i, b = j;
}
int l = 0;
bool bl = 1;
for (int i = 0; i < n; i++)
{
if(i==a||i==b) continue;
int c = (d[a][i] + d[a][b] - d[i][b]) / 2;
if(max(l, d[a][b] - l) > max(c, d[a][b] - c)) l = c;
else if(max(l, d[a][b] - l) == max(c, d[a][b] - c)) l = max(l, c);
}
bl = stg(l, a, b);
l = 0;
for (int i = 0; i < n; i++)
{
if(i==a||i==b) continue;
int c = (d[a][i] + d[a][b] - d[i][b]) / 2;
if(max(l, d[a][b] - l) > max(c, d[a][b] - c)) l = c;
else if(max(l, d[a][b] - l) == max(c, d[a][b] - c)) l = min(l, c);
}
if(bl || stg(l, a, b)) return max(l, d[a][b] - l);
else return -max(l, d[a][b] - l);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) d[i][j] = 0;
int a = 0;
for (int i = 1; i < n; i++)
{
d[0][i] = d[i][0] = getDistance(0, i);
if(d[0][i] > d[0][a]) a = i;
}
int b = 0;
for (int i = 1; i < n; i++)
{
if(a == i) continue;
d[a][i] = d[i][a] = getDistance(a, i);
if(d[a][i] > d[a][b]) b = i;
}
int pat = d[a][b];
int sm = (d[a][0] + d[0][b] - d[a][b]) / 2;
sm = d[a][0] - sm;
int i1 = 0;
//cout << sm << endl;
for (int i = 0; i < n; i++)
{
if(i == a || i == b) continue;
if(b == 0 || i == 0)
{
int c = (d[a][i]+d[i][b] - d[a][b]) / 2;
pat = min(pat, max(d[a][i], d[i][b]) - c);
}
else
{
int l = (d[a][i1] + d[i1][i] - d[a][i]) / 2;
l = d[a][i1] - l;
if(sm > l) pat = min(pat, max(l, d[a][b] - l));
else if(sm == l)
{
d[b][i] = d[i][b] = getDistance(b, i);
int c = (d[a][i] + d[a][b] - d[b][i]) / 2;
pat = min(pat, max(c, d[a][b] - c));
}
}
}
return pat;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:36:21: warning: declaration of 'N' shadows a global declaration [-Wshadow]
36 | int hubDistance(int N, int sub)
| ~~~~^
towns.cpp:5:11: note: shadowed declaration is here
5 | const int N = 150;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
332 KB |
Output is correct |
| 2 |
Correct |
17 ms |
392 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
18 ms |
400 KB |
Output is correct |
| 5 |
Correct |
18 ms |
400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
404 KB |
Output is correct |
| 2 |
Correct |
13 ms |
404 KB |
Output is correct |
| 3 |
Correct |
20 ms |
384 KB |
Output is correct |
| 4 |
Correct |
19 ms |
400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
388 KB |
Output is correct |
| 2 |
Correct |
20 ms |
904 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
26 ms |
936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
332 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
