| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1018897 |
2024-07-10T10:43:05 Z |
AmirAli_H1 |
Towns (IOI15_towns) |
C++17 |
|
12 ms |
1116 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(23232323);
int n, vx;
const int maxn = 110 + 4;
ll dis[maxn][maxn];
ll D1[maxn], D2[maxn];
ll ans, R, dx; bool f1, f2, ok;
int p[maxn], sz[maxn], mark[maxn];
vector<int> ls;
int get(int a) {
return (p[a] == a) ? a : p[a] = get(p[a]);
}
void merge(int a, int b) {
a = get(a); b = get(b);
if (a == b) return ;
if (sz[a] > sz[b]) swap(a, b);
p[a] = b; sz[b] += sz[a]; sz[a] = 0;
}
int get_dis(int u, int v) {
if (dis[u][v] == -1) {
dis[u][v] = dis[v][u] = getDistance(u, v);
}
return dis[u][v];
}
void calx() {
f1 = 0, f2 = 0; ok = 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;
}
int t1 = 0, t2 = 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++;
}
if (max(t1, t2) * 2 <= n) ok = 1;
t1 = 0, t2 = 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++;
}
if (max(t1, t2) * 2 <= n) ok = 1;
}
void solve3() {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
ll x1 = (D1[i] + D2[i] - dx) / 2;
ll x2 = (D1[j] + D2[j] - dx) / 2;
ll d = (x1 + x2 - get_dis(i, j)) / 2;
if (d > 0) merge(i, j);
}
}
int mx = *max_element(sz, sz + n);
if (2 * mx > n) ans = -ans;
return ;
}
void solve4() {
if (f1) {
int t = 0;
for (int i = 0; i < n; i++) {
ll x = (D1[i] + D2[i] - dx) / 2;
ll d = D1[i] - x;
if (d == R) t++;
}
if (2 * t <= n) return ;
}
if (f2) {
int t = 0;
for (int i = 0; i < n; i++) {
ll x = (D1[i] + D2[i] - dx) / 2;
ll d = D2[i] - x;
if (d == R) t++;
}
if (2 * t <= n) return ;
}
ans = -ans;
return ;
}
void solvex() {
fill(mark, mark + n, 0);
int i = -1;
for (int T = 0; T < 3; T++) {
ls.clear();
for (int j = 0; j < n; j++) {
if (!mark[j]) ls.pb(j);
}
if (i == -1) i = vx;
else i = ls[rng() % len(ls)];
mark[i] = 1;
for (int j = 0; j < n; j++) {
if (i == j) continue;
ll x1 = (D1[i] + D2[i] - dx) / 2;
ll x2 = (D1[j] + D2[j] - dx) / 2;
ll d = (x1 + x2 - get_dis(i, j)) / 2;
if (d > 0) {
merge(i, j); mark[j] = 1;
}
}
if (sz[get(i)] * 2 > n) {
ans = -ans;
return ;
}
}
return ;
}
int hubDistance(int N, int sub) {
n = N;
iota(p, p + n, 0); fill(sz, sz + n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) dis[i][j] = 0;
else dis[i][j] = -1;
}
}
vx = rng() % n;
ll mx = 0; int u1 = vx;
for (int i = 0; i < n; i++) {
if (i == 0) continue;
ll d = get_dis(vx, 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] = get_dis(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] = get_dis(u2, i);
}
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));
}
ans = R;
calx();
if (!ok) return -ans;
if (sub == 3) solve3();
else if (sub == 4) solve4();
else if (sub >= 5) solvex();
return ans;
}
Compilation message
towns.cpp: In function 'int get_dis(int, int)':
towns.cpp:49:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
49 | return dis[u][v];
| ~~~~~~~~^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:159:13: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
159 | vx = rng() % n;
| ~~~~~~^~~
towns.cpp:197:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
197 | if (!ok) return -ans;
| ^~~~
towns.cpp:203:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
203 | return ans;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
860 KB |
Output is correct |
| 2 |
Correct |
7 ms |
860 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1092 KB |
Output is correct |
| 5 |
Correct |
10 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
348 KB |
Output is correct |
| 2 |
Correct |
7 ms |
860 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
860 KB |
Output is correct |
| 2 |
Correct |
10 ms |
928 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
10 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
