This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 505;
int x, y;
int D0[Nmax], D1[Nmax], D2[Nmax], Up[Nmax], L[Nmax], R[Nmax];
map< int, vector<int> > gr;
map< pair<int,int> , int > mp;
int getDist(int x, int y)
{
if(x == y) return 0;
if(mp[{x,y}]) return mp[{x, y}];
return mp[{x, y}] = mp[{y, x}] = getDistance(x, y);
}
void prepare(int n)
{
int i;
for(i=0; i<n; ++i) D0[i] = getDist(0, i);
x = max_element(D0, D0+n) - D0;
for(i=0; i<n; ++i) D1[i] = getDist(x, i);
y = max_element(D1, D1+n) - D1;
for(i=0; i<n; ++i) D2[i] = getDist(y, i);
}
bool check(vector<int> &v, int n)
{
if(v.size() <= n/2) return 1;
int candidat = v[0];
int cnt = 0;
for(auto it : v)
if(getDist(candidat, it) == Up[candidat] + Up[it]) /// bucketuri diferite
{
if(!cnt) candidat = it, cnt = 1;
else --cnt;
}
else ++cnt;
cnt = v.size();
for(auto it : v)
if(getDist(candidat, it) == Up[candidat] + Up[it]) --cnt;
return (cnt <= n/2);
}
int hubDistance(int n, int subtask)
{
gr.clear();
mp.clear();
prepare(n);
int total = D1[y];
int ans = 2e9;
int i;
for(i=0; i<n; ++i)
{
Up[i] = D1[i] + D2[i] - total;
assert(Up[i] % 2 == 0);
Up[i] /= 2;
L[i] = D1[i] - Up[i];
R[i] = D2[i] - Up[i];
assert(L[i] + R[i] == total);
gr[L[i]].push_back(i);
ans = min(ans, max(L[i], R[i]));
}
if(subtask <= 2) return ans;
bool balanced = 0;
int cnt1 = 0, cnt2 = n;
for(auto &it : gr)
{
assert(it.second.size());
cnt2 -= it.second.size();
if(max(it.first, total - it.first) == ans && cnt1 <= n/2 && cnt2 <= n/2)
balanced |= check(it.second, n);
cnt1 += it.second.size();
}
return ans * (balanced ? 1 : -1);
}
Compilation message (stderr)
towns.cpp: In function 'int getDist(int, int)':
towns.cpp:14:25: warning: declaration of 'y' shadows a global declaration [-Wshadow]
int getDist(int x, int y)
^
towns.cpp:8:8: note: shadowed declaration is here
int x, y;
^
towns.cpp:14:25: warning: declaration of 'x' shadows a global declaration [-Wshadow]
int getDist(int x, int y)
^
towns.cpp:8:5: note: shadowed declaration is here
int x, y;
^
towns.cpp: In function 'void prepare(int)':
towns.cpp:26:31: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
x = max_element(D0, D0+n) - D0;
~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:30:31: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
y = max_element(D1, D1+n) - D1;
~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp: In function 'bool check(std::vector<int>&, int)':
towns.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(v.size() <= n/2) return 1;
~~~~~~~~~^~~~~~
towns.cpp:51:17: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
cnt = v.size();
~~~~~~^~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:94:32: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
cnt2 -= it.second.size();
^
towns.cpp:99:32: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
cnt1 += it.second.size();
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |