#include "bits/stdc++.h"
#define TESTING 0
#include "towns.h"
#if TESTING
#include "graderlib.c"
#endif
using namespace std;
typedef long long BEEG;
typedef unsigned long long uBEEG;
int n, root = 0, second = -1;
map<pair<int, int>, int> dists;
map<int, vector<int>> diam;
vector<int> diamdists, offshootpref, diamdiffs, distpref;
pair<int, int> getPair(int a, int b)
{
int smol = min(a, b);
int big = a + b - smol;
return {smol, big};
}
int getEdge(int a, int b)
{
if(a == b) return 0;
auto edge = getPair(a, b);
if(dists.count(edge) == 0)
{
dists[edge] = getDistance(a, b);
}
return dists[edge];
}
int hubDistance(int N, int sub)
{
n = N;
int big = 0, bigdist = 0;
for(int i = 1; i < N; i++)
{
int dist = getEdge(root, i);
if(dist > bigdist)
{
bigdist = dist;
big = i;
}
}
root = big;
if(TESTING) cerr << "Root: " << root << "\n";
big = 0;
for(int i = 0; i < N; i++)
{
if(i == root) continue;
int dist = getEdge(root, i);
if(dist > bigdist)
{
bigdist = dist;
big = i;
}
}
second = big;
if(TESTING) cerr << "Second: " << second << "\n";
for(int i = 0; i < N; i++)
{
int rootDist = getEdge(root, i), secDist = getEdge(second, i);
int diff = rootDist - secDist;
diam[diff].push_back(i);
}
int c = 0;
diamdists.resize(diam.size() - 1, 0);
diamdiffs.resize(diam.size(), 0);
diamdiffs[0] = diam.begin()->first;
int prev = INT_MAX;
for(auto& it : diam)
{
if(prev != INT_MAX)
{
diamdists[c++] = (it.first - prev) / 2;
diamdiffs[c] = it.first;
}
prev = it.first;
}
if(TESTING)
{
cerr << "Diamdists: ";
for(int i = 0; i < diamdists.size(); i++) cerr << diamdists[i] << " ";
cerr << "\n";
}
offshootpref.resize(diam.size(), 0);
offshootpref[0] = 1;
for(int i = 1; i < diam.size(); i++)
{
offshootpref[i] = offshootpref[i - 1] + diam[diamdiffs[i]].size();
}
if(TESTING)
{
cerr << "Nodes Prefix: ";
for(int i = 0; i < offshootpref.size(); i++) cerr << offshootpref[i] << " ";
cerr << "\n";
}
distpref.resize(diam.size(), 0);
for(int i = 1; i < diam.size(); i++)
{
distpref[i] = distpref[i-1] + diamdists[i - 1];
}
if(TESTING)
{
cerr << "Dist Prefix: ";
for(int i = 0; i < distpref.size(); i++) cerr << distpref[i] << " ";
cerr << "\n";
}
int R = INT_MAX;
vector<int> hubs;
for(int i = 0; i < diam.size(); i++)
{
int rc = distpref[i];
rc = max(rc, distpref.back() - distpref[i]);
if(rc < R)
{
R = rc;
hubs.clear();
hubs.push_back(i);
if(TESTING) cerr << "New R: " << R << "\n" << "New hub: " << i << "\n";
}
else if(rc == R)
{
hubs.push_back(i);
if(TESTING) cerr << "New hub: " << i << "\n";
}
}
//decide if multiply by negative
return R;
}
#if TESTING
int main() {
FILE *f;
f = freopen("towns.in","r",stdin);
assert(f != NULL);
f = freopen("towns.out","w",stdout);
assert(f != NULL);
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\n",R);
}
return 0;
}
#endif
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i = 0; i < diamdists.size(); i++) cerr << diamdists[i] << " ";
| ~~^~~~~~~~~~~~~~~~~~
towns.cpp:111:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i = 1; i < diam.size(); i++)
| ~~^~~~~~~~~~~~~
towns.cpp:113:47: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
113 | offshootpref[i] = offshootpref[i - 1] + diam[diamdiffs[i]].size();
towns.cpp:119:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i = 0; i < offshootpref.size(); i++) cerr << offshootpref[i] << " ";
| ~~^~~~~~~~~~~~~~~~~~~~~
towns.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int i = 1; i < diam.size(); i++)
| ~~^~~~~~~~~~~~~
towns.cpp:132:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for(int i = 0; i < distpref.size(); i++) cerr << distpref[i] << " ";
| ~~^~~~~~~~~~~~~~~~~
towns.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int i = 0; i < diam.size(); i++)
| ~~^~~~~~~~~~~~~
towns.cpp:40:28: warning: unused parameter 'sub' [-Wunused-parameter]
40 | int hubDistance(int N, int sub)
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
456 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
