# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
714880 |
2023-03-25T11:36:41 Z |
lam |
Towns (IOI15_towns) |
C++14 |
|
15 ms |
1100 KB |
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
#define ff first
#define ss second
const int maxn = 510;
int n;
int d[maxn][maxn];
int ds[maxn],up[maxn];
map<ii,int> cnt;
int Ask(int u, int v)
{
if (u==v) return 0;
if (u>v) swap(u,v);
if (d[u][v] == -1)
{
d[u][v] = getDistance(u,v);
// cerr<<u<<" - "<<v<<" = "<<d[u][v]<<endl;
}
return d[u][v];
}
bool check(int dist)
{
vector<int> to_mid(n+1,0);
for (int i=0; i<n; i++)
if (ds[i]<dist) to_mid[i]=dist-ds[i]+up[i];
else to_mid[i]=ds[i]-dist+up[i];
vector <int> sz(n+1,0);
int alive = 0; int num=1;
for (int i=1; i<n; i++)
if (num==0)
{
num=1;
sz[i]++; alive=i;
}
else
{
if (Ask(i,alive)==to_mid[i]+to_mid[alive])
{
num--; sz[i]++;
}
else
{
num++;
sz[alive]++;
}
}
if (num<=0) return 1;
num=0;
for (int i=0; i<n; i++) if (sz[i]!=0)
{
if (Ask(i,alive)==to_mid[i]+to_mid[alive]) num-=sz[i];
else num+=sz[i];
}
return num<=0;
}
int hubDistance(int N, int sub) {
n=N;
cnt.clear();
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) d[i][j] = -1;
int u,v,dist; dist=0;
u=0;
for (int i=1; i<n; i++) if (dist<Ask(0,i))
{
u=i;
dist=Ask(0,i);
}
v=0; dist=Ask(0,u);
for (int i=1; i<n; i++) if (dist<Ask(u,i))
{
dist=Ask(u,i);
v=i;
}
int R=1e9;
for (int i=0; i<n; i++)
{
int x=Ask(u,i); int y=Ask(i,0);
int z=Ask(u,0);
up[i] = (x+y-z)/2;
ds[i] = x-up[i];
// cout<<x<<' '<<y<<' '<<z<<'\n';
// cout<<i<<" := "<<up[i]<<' '<<ds[i]<<'\n';
R=min(R,max(ds[i],dist-ds[i]));
cnt[{ds[i],dist-ds[i]}]++;
}
int sum = 0;
int it = 0;
int dau = -1;
for (auto i:cnt)
{
int sz = i.ss;
if (max(i.ff.ff,i.ff.ss)==R)
{
if (sz<=n/2&&sum<=n/2&&(n-sz-sum)<=n/2)
{
dau=1;
it=0;
break;
}
else if (sum<=n/2&&(n-sz-sum)<=n/2)
{
it=i.ff.ff;
}
}
sum+=sz;
}
if (it!=0)
{
if (check(it)) dau=1;
else dau=-1;
}
return dau*R;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:65:11: warning: variable 'v' set but not used [-Wunused-but-set-variable]
65 | int u,v,dist; dist=0;
| ^
towns.cpp:60:28: warning: unused parameter 'sub' [-Wunused-parameter]
60 | int hubDistance(int N, int sub) {
| ~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
468 KB |
Output is correct |
2 |
Correct |
13 ms |
468 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
13 ms |
556 KB |
Output is correct |
5 |
Correct |
12 ms |
552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
468 KB |
Output is correct |
2 |
Correct |
10 ms |
468 KB |
Output is correct |
3 |
Correct |
12 ms |
556 KB |
Output is correct |
4 |
Correct |
12 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
556 KB |
Output is correct |
2 |
Correct |
14 ms |
1052 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
13 ms |
1048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
468 KB |
Output is correct |
2 |
Correct |
13 ms |
548 KB |
Output is correct |
3 |
Correct |
15 ms |
1100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
556 KB |
Output is correct |
2 |
Correct |
13 ms |
1056 KB |
Output is correct |
3 |
Correct |
13 ms |
1096 KB |
Output is correct |