| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1018768 |
2024-07-10T09:37:34 Z |
AmirAli_H1 |
Towns (IOI15_towns) |
C++17 |
|
10 ms |
352 KB |
// In the name of Allah
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
const int maxn = 110 + 4;
ll D1[maxn], D2[maxn];
int hubDistance(int N, int sub) {
n = N;
ll mx = 0; int u1 = 0;
for (int i = 0; i < n; i++) {
if (i == 0) continue;
ll d = getDistance(0, i);
if (d >= mx) {
mx = d; u1 = i;
}
}
mx = 0; int u2 = u1;
for (int i = 0; i < n; i++) {
if (i == u1) {
D1[i] = 0;
continue;
}
D1[i] = getDistance(u1, i);
if (D1[i] >= mx) {
mx = D1[i]; u2 = i;
}
}
for (int i = 0; i < n; i++) {
if (i == u2) {
D2[i] = 0;
continue;
}
D2[i] = getDistance(u2, i);
}
ll dx = D1[u2], R = dx;
for (int i = 0; i < n; i++) {
ll x = (D1[i] + D2[i] - dx) / 2;
R = min(R, max(D1[i] - x, D2[i] - x));
}
if (sub == 3) {
}
else if (sub == 4) {
bool f1 = 0, f2 = 0;
for (int i = 0; i < n; i++) {
ll x = (D1[i] + D2[i] - dx) / 2;
if (D1[i] - x == R) f1 = 1;
if (D2[i] - x == R) f2 = 1;
}
if (f1) {
int t1 = 0, t2 = 0, t3 = 0;
for (int i = 0; i < n; i++) {
ll x = (D1[i] + D2[i] - dx) / 2;
ll d = D1[i] - x;
if (d == R) t1++;
else if (d < R) t2++;
else t3++;
}
if (2 * max({t1, t2, t3}) <= n) return R;
}
if (f2) {
int t1 = 0, t2 = 0, t3 = 0;
for (int i = 0; i < n; i++) {
ll x = (D1[i] + D2[i] - dx) / 2;
ll d = D2[i] - x;
if (d == R) t1++;
else if (d < R) t2++;
else t3++;
}
if (2 * max({t1, t2, t3}) <= n) return R;
}
return -R;
}
return R;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:88:43: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
88 | if (2 * max({t1, t2, t3}) <= n) return R;
| ^
towns.cpp:99:43: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
99 | if (2 * max({t1, t2, t3}) <= n) return R;
| ^
towns.cpp:101:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
101 | return -R;
| ^~
towns.cpp:103:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
103 | return R;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
348 KB |
Output is correct |
| 2 |
Correct |
10 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
9 ms |
348 KB |
Output is correct |
| 5 |
Correct |
10 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
348 KB |
Output is correct |
| 2 |
Correct |
7 ms |
348 KB |
Output is correct |
| 3 |
Correct |
10 ms |
348 KB |
Output is correct |
| 4 |
Correct |
10 ms |
352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
