#include "towns.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 256;
int D[N][N];
int get(int x,int y) {
if (D[x][y] != -1)
return D[x][y];
return D[x][y] = D[y][x] = getDistance(x,y);
}
int hubDistance(int n, int sub) {
srand(time(0));
const int root = 0;
memset(D,-1,sizeof(D));
int x = 0;
for (int i = 0;i < n;++i)
D[i][i] = 0;
for (int i = 0;i < n;++i)
if (get(root,i) > get(root,x))
x = i;
int y = x;
for (int i = 0;i < n;++i)
if (get(x,i) > get(x,y))
y = i;
const int Diam = get(x,y);
int ans = 2e9;
vi dist(n,0);
for (int i = 0;i < n;++i) {
dist[i] = (get(root,i) + get(x,i) - get(root,x)) / 2;
int dx = get(x,i) - dist[i];
smin(ans,max(Diam - dx,dx));
}
return ans;
auto ok = [&](int A,int B) {
return get(A,B) != dist[A] + dist[B];
};
return ans;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:29:12: warning: conversion to 'unsigned int' from 'time_t {aka long int}' may alter its value [-Wconversion]
srand(time(0));
~~~~^~~
towns.cpp:51:7: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
auto ok = [&](int A,int B) {
^~
towns.cpp:28:28: warning: unused parameter 'sub' [-Wunused-parameter]
int hubDistance(int n, int sub) {
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
632 KB |
Output is correct |
2 |
Correct |
18 ms |
740 KB |
Output is correct |
3 |
Correct |
3 ms |
740 KB |
Output is correct |
4 |
Correct |
28 ms |
740 KB |
Output is correct |
5 |
Correct |
23 ms |
760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
760 KB |
Output is correct |
2 |
Correct |
21 ms |
760 KB |
Output is correct |
3 |
Correct |
35 ms |
772 KB |
Output is correct |
4 |
Correct |
27 ms |
772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
772 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
30 ms |
808 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
16 ms |
808 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
20 ms |
808 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |