| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 802491 |
2023-08-02T12:32:53 Z |
caganyanmaz |
Towns (IOI15_towns) |
C++17 |
|
12 ms |
352 KB |
#include <bits/stdc++.h>
#define pb push_back
#include "towns.h"
using namespace std;
constexpr static int INF = 2e9;
constexpr static int MXSIZE = 110;
int n;
vector<int> ll, ml, mr, rr;
int ldist[MXSIZE];
int rdist[MXSIZE];
int fdist[MXSIZE];
bool connected(int i, int j, int* dist, int cndist)
{
int cdist;
if (!i)
cdist = fdist[j];
if (!j)
cdist = fdist[i];
else
cdist = getDistance(i, j);
bool res = dist[i] + dist[j] > (cdist + cndist * 2);
return res;
}
bitset<MXSIZE> visited;
vector<int> g[MXSIZE];
int dfs(int node)
{
visited[node] = true;
int sum = 1;
for (int c : g[node])
if (!visited[c])
sum += dfs(c);
return sum;
}
bool check(const vector<int>& v, int* dist, int cndist)
{
for (int i = 0; i < v.size(); i++)
{
for (int j = i+1; j < v.size(); j++)
{
if (connected(v[i], v[j], dist, cndist))
{
g[v[i]].pb(v[j]);
g[v[j]].pb(v[i]);
}
}
}
int mxsize = 0;
for (int i : v)
if (!visited[i])
mxsize = max(mxsize, dfs(i));
return mxsize <= (n/2);
}
int hubDistance(int N, int sub)
{
n = N;
int mxdist = 0;
int j = 0;
for (int i = 1; i < n; i++)
{
int val = getDistance(0, i);
fdist[i] = val;
if (val > mxdist)
{
j = i;
mxdist = val;
}
}
int k = 0;
ldist[0] = mxdist;
for (int i = 1; i < n; i++)
{
if (i == j)
continue;
int val = getDistance(i, j);
ldist[i] = val;
if (val > mxdist)
{
k = i;
mxdist = val;
}
}
int r = mxdist;
for (int i = 0; i < n; i++)
{
if (i == j || i == k)
continue;
int da = ldist[i];
int db = getDistance(i, k);
rdist[i] = db;
int change = (da + db - mxdist) / 2;
r = min(r, max(da - change, db - change));
}
if (sub <= 2)
return r;
return -r;
ll.pb(j);
rr.pb(k);
for (int i = 0; i < n; i++)
{
if (i == j || i == k)
continue;
int change = (ldist[i] + rdist[i] - mxdist) / 2;
if (r == max(ldist[i] - change, rdist[i] - change) && ldist[i] <= rdist[i])
ml.pb(i);
else if (r == max(ldist[i] - change, rdist[i] - change))
mr.pb(i);
else if (ldist[i] < rdist[i])
ll.pb(i);
else if (ldist[i] > rdist[i])
rr.pb(i);
else
assert(false);
}
if (ll.size() > (n/2) || rr.size() > (n/2))
return -r;
bool res;
int cndist;
if ((ll.size() + ml.size()) > (rr.size() + mr.size()))
{
if (ml.empty())
{
res = true;
}
else
{
cndist = ldist[ml[0]] - rdist[ml[0]] + r;
res = check(ml, ldist, cndist);
}
}
else
{
if (mr.empty())
{
res = true;
}
else
{
cndist = rdist[mr[0]] - ldist[mr[0]] + r;
res = check(mr, rdist, cndist);
}
}
if (res)
return r;
else
return -r;
}
Compilation message
towns.cpp: In function 'bool check(const std::vector<int>&, int*, int)':
towns.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
towns.cpp:48:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int j = i+1; j < v.size(); j++)
| ~~^~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:126:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
126 | if (ll.size() > (n/2) || rr.size() > (n/2))
| ~~~~~~~~~~^~~~~~~
towns.cpp:126:44: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
126 | if (ll.size() > (n/2) || rr.size() > (n/2))
| ~~~~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
348 KB |
Output is correct |
| 2 |
Correct |
8 ms |
352 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
12 ms |
344 KB |
Output is correct |
| 5 |
Correct |
11 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
348 KB |
Output is correct |
| 2 |
Correct |
9 ms |
340 KB |
Output is correct |
| 3 |
Correct |
12 ms |
340 KB |
Output is correct |
| 4 |
Correct |
12 ms |
352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
