# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
398592 |
2021-05-04T15:12:04 Z |
MKopchev |
Towns (IOI15_towns) |
C++14 |
|
22 ms |
392 KB |
#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
/*
static int _N;
static int _dist[110][110];
static int _quota, _user_query;
void _ini_query(int N, int k) {
int ret;
_N = N;
for (int i = 0; i < _N; i++)
for (int j = 0; j < _N; j++) {
ret = scanf("%d", &_dist[i][j]);
assert(ret == 1);
}
if (k == 1 || k == 3) _quota = _N * (_N - 1) / 2;
else if (k == 2 || k == 4 || k == 6) _quota = (7 * _N + 1) / 2;
else _quota = 5 * _N;
_user_query = 0;
}
int getDistance(int i, int j) {
_user_query++;
if (_user_query > _quota) {
printf("0\n");
exit(0);
}
if (i < 0 || i >= _N) return 0;
if (j < 0 || j >= _N) return 0;
return _dist[i][j];
}
*/
map< pair<int,int>,int> seen;
int my_getDistance(int i,int j)
{
if(i==j)return 0;
if(seen.count({i,j}))return seen[{i,j}];
int d=getDistance(i,j);
seen[{i,j}]=d;
seen[{j,i}]=d;
return d;
}
int hubDistance(int n, int subtask)
{
seen={};
int u=1;
for(int i=2;i<n;i++)
{
if(my_getDistance(0,u)<my_getDistance(0,i))u=i;
}
int v=0;
for(int i=1;i<n;i++)
{
if(my_getDistance(u,v)<my_getDistance(u,i))v=i;
}
//cout<<"diameter "<<u<<" "<<v<<endl;
int outp=1e9;
for(int i=0;i<n;i++)
if(i!=u&&i!=v)
{
int cur=my_getDistance(0,u)+my_getDistance(u,i)-my_getDistance(0,i);
cur=cur/2;
outp=min(outp,max(cur,my_getDistance(v,u)-cur));
//cout<<i<<" -> "<<cur<<endl;
}
map<int,int> seen={};
for(int i=1;i<n;i++)
if(i!=u)
{
int d=my_getDistance(0,i)+my_getDistance(0,u)-my_getDistance(i,u);
d=d/2;
seen[d]++;
//cout<<i<<" -> "<<d<<endl;
}
int wanted=-1;
int sum=1;
for(auto w:seen)
{
int remain=n-sum-w.second;
//cout<<w.second<<" "<<sum<<" "<<remain<<endl;
if(remain<=n/2&&sum<=n/2&&w.second<=n/2)return outp;
if(remain<=n/2&&sum<=n/2)wanted=w.first;
sum+=w.second;
}
if(wanted==-1)return -outp;
vector<int> remain={};
for(int i=1;i<n;i++)
if(i!=u)
{
int d=my_getDistance(0,i)+my_getDistance(0,u)-my_getDistance(i,u);
d=d/2;
if(d==wanted)remain.push_back(i);
}
//for(auto w:remain)cout<<w<<" ";cout<<endl;
pair<int,int> maj={0,0};
for(auto w:remain)
{
if(maj.second==0)maj={w,1};
else
{
if(my_getDistance(w,maj.first)==my_getDistance(0,w)-wanted+my_getDistance(0,maj.first)-wanted)maj.second--;
else maj.second++;
}
}
maj.second=0;
for(auto w:remain)
{
if(my_getDistance(w,maj.first)!=my_getDistance(0,w)-wanted+my_getDistance(0,maj.first)-wanted)maj.second++;
}
if(maj.second>n/2)return -outp;
return outp;
}
/*
int main()
{
int ncase, R, N;
int subtask;
int ret;
ret = scanf("%d%d",&subtask,&ncase);
assert(ret == 2);
for (int i = 0; i < ncase; i++) {
ret = scanf("%d",&N);
assert(ret == 1);
_ini_query(N,subtask);
R=hubDistance(N,subtask);
printf("%d %d\n",R,_user_query);
}
}
*/
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:78:18: warning: declaration of 'seen' shadows a global declaration [-Wshadow]
78 | map<int,int> seen={};
| ^~~~
towns.cpp:35:25: note: shadowed declaration is here
35 | map< pair<int,int>,int> seen;
| ^~~~
towns.cpp:48:28: warning: unused parameter 'subtask' [-Wunused-parameter]
48 | int hubDistance(int n, int subtask)
| ~~~~^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
384 KB |
Output is correct |
2 |
Incorrect |
22 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
376 KB |
Output is correct |
2 |
Incorrect |
18 ms |
332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
332 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
380 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |