| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 288584 |
2020-09-01T16:19:09 Z |
Kastanda |
Towns (IOI15_towns) |
C++11 |
|
26 ms |
640 KB |
// M
#include<bits/stdc++.h>
#include "towns.h"
using namespace std;
const int N = 119;
int n, sub, D[N][N], A[N], F[N], P[N];
vector < int > Fail[N];
inline int Dist(int a, int b)
{
if (a == b)
return 0;
if (D[a][b] != -1)
return D[a][b];
D[a][b] = D[b][a] = getDistance(a, b);
return D[a][b];
}
int Find(int v)
{
return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u)
{
v = Find(v);
u = Find(u);
if (v == u)
return ;
for (int a : Fail[u])
Fail[v].push_back(a);
Fail[u].clear();
P[v] += P[u];
P[u] = v;
}
inline int Oracle(int v, int u)
{
v = Find(v);
u = Find(u);
if (v == u)
return 1;
for (int a : Fail[v])
if (Find(a) == u)
return 0;
for (int a : Fail[u])
if (Find(a) == v)
return 0;
return -1;
}
inline bool SameComp(int v, int u)
{
int w = Oracle(v, u);
if (w != -1)
return w;
assert(Find(v) != Find(u));
if (Dist(v, u) < A[v] + A[u])
{
Merge(v, u);
return 1;
}
else
{
Fail[Find(v)].push_back(Find(u));
Fail[Find(u)].push_back(Find(v));
return 0;
}
}
int shdbe = -1;
void Solve(vector < int > vec)
{
int odd = -1;
if ((int)vec.size() & 1)
odd = vec.back(), vec.pop_back();
vector < int > sames;
for (int i = 1; i < (int)vec.size(); i += 2)
if (SameComp(vec[i - 1], vec[i]))
sames.push_back(vec[i]);
if ((int)sames.size() == 1)
{
shdbe = sames[0];
return ;
}
if ((int)sames.size() > 1)
Solve(sames);
if (shdbe != -1)
return ;
if (odd != -1)
{
shdbe = odd;
return ;
}
return ;
}
inline bool isOkay(vector < int > vec, int szlim)
{
memset(P, -1, sizeof(P));
for (int i = 0; i < n; i ++)
Fail[i].clear();
shdbe = -1;
Solve(vec);
if (shdbe == -1)
return 1;
int cnt = 0;
for (int v : vec)
if (SameComp(v, shdbe))
{
cnt ++;
if (cnt > szlim)
return 0;
}
return 1;
}
int hubDistance(int _n, int _sub)
{
n = _n; sub = _sub;
memset(D, -1, sizeof(D));
int diam1 = 0;
for (int i = 1; i < n; i ++)
if (Dist(0, i) > Dist(0, diam1))
diam1 = i;
int diam2 = 0;
for (int i = 0; i < n; i ++)
if (Dist(diam1, i) > Dist(diam1, diam2))
diam2 = i;
// Corner cases : diam2 = 0 ?
F[0] = (Dist(0, diam1) - Dist(0, diam2) + Dist(diam1, diam2)) / 2;
A[0] = Dist(0, diam1) - F[0];
int Rad = INT_MAX;
vector < int > Centre;
for (int i = 1; i < n; i ++)
{
int df = Dist(i, diam1) - Dist(i, 0) + Dist(diam1, 0);
df /= 2;
if (df >= F[0])
df = F[0];
A[i] = Dist(i, diam1) - df;
F[i] = df;
if (Rad > max(df, Dist(diam1, diam2) - df))
Rad = max(df, Dist(diam1, diam2) - df), Centre.clear();
if (Rad == max(df, Dist(diam1, diam2) - df))
Centre.push_back(df);
}
sort(Centre.begin(), Centre.end());
Centre.resize(unique(Centre.begin(), Centre.end()) - Centre.begin());
assert((int)Centre.size() <= 2);
if (sub <= 2)
return Rad;
int szlim = n / 2, cc = 0;
for (int centroid : Centre)
{
vector < int > vec;
int cle = 0, cri = 0, cmd = 0;
for (int i = 0; i < n; i ++)
{
if (F[i] < centroid)
cle ++;
else if (F[i] > centroid)
cri ++;
else
cmd ++, vec.push_back(i);
}
if (cle > szlim || cri > szlim)
continue;
if (cmd <= szlim)
return Rad;
cc ++;
assert(cc == 1);
if (isOkay(vec, szlim))
return Rad;
}
return -Rad;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
384 KB |
Output is correct |
| 2 |
Correct |
16 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
22 ms |
384 KB |
Output is correct |
| 5 |
Correct |
22 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
384 KB |
Output is correct |
| 2 |
Correct |
16 ms |
384 KB |
Output is correct |
| 3 |
Correct |
26 ms |
464 KB |
Output is correct |
| 4 |
Correct |
22 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
384 KB |
Output is correct |
| 2 |
Correct |
22 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
22 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
384 KB |
Output is correct |
| 2 |
Correct |
22 ms |
608 KB |
Output is correct |
| 3 |
Correct |
22 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
384 KB |
Output is correct |
| 2 |
Correct |
23 ms |
384 KB |
Output is correct |
| 3 |
Correct |
22 ms |
512 KB |
Output is correct |
