| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 64745 |
2018-08-05T13:55:02 Z |
FLDutchman |
Towns (IOI15_towns) |
C++14 |
|
32 ms |
820 KB |
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define pb push_back
#define fst first
#define snd second
#define LSB(k) k&-k
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
const int mod = 1e9+7;
int D;
INT hubDistance(INT N, INT sub) {
vvi dist(N);
FOR(i, 0, N) FOR(j, 0, N){
if(j < i) dist[i].pb(dist[j][i]);
else if (j == i) dist[i].pb(0);
else dist[i].pb(getDistance(i, j));
}
ii far = {-1, -1};
FOR(i, 1, N) far = max(far, {dist[0][i], i});
int I = far.snd;
far = {-1, -1};
FOR(i, 0, N) far = max(far, {dist[I][i], i});
int J = far.snd;
D = far.fst;
map<int, vi> pts;
int R = 1e9;;
FOR(i, 0, N){
int d = (dist[I][i] + dist[J][i] - D)/2;
pts[dist[I][i]-d].pb(i);
R = min(R, max(dist[I][i]-d, dist[J][i] - d));
}
int e = 0;
bool poss = false;
if(!pts[R].empty()){
// R is a possible balanced hub
int largest = 0;
vi counted(N, 0);
for(int i : pts[R]){
if(!counted[i]){
int sz = 1;
counted[i] = 1;
int d = (dist[I][i] + dist[J][i] - D)/2;
for(int j : pts[R]) if(!counted[j]){
if(dist[I][j] - R + d != dist[I][i]) {
sz++;
counted[j] = 1;
}
}
largest = max(sz, largest);
}
}
if(largest <= N/2) poss = true;
}
if(!pts[D - R].empty()){
R = D - R;
// R is a possible balanced hub
int largest = 0;
vi counted(N, 0);
for(int i : pts[R]){
if(!counted[i]){
int sz = 1;
counted[i] = 1;
int d = (dist[I][i] + dist[J][i] - D)/2;
for(int j : pts[R]) if(!counted[j]){
if(dist[I][j] - R + d != dist[I][i]) {
sz++;
counted[j] = 1;
}
}
largest = max(sz, largest);
}
}
R = D - R;
if(largest <= N/2) poss = true;
}
if(!poss) return -R;
int r2 = D - R;
// amnt < R, = R, > R
int l = 0, g = 0;
int L = 0, G = 0;
for(auto it : pts){
if(pts[R].size() != 0){
if(it.fst < R) l += it.snd.size();
if(it.fst > R) g += it.snd.size();
}
if(pts[r2].size() != 0){
if(it.fst < r2) L += it.snd.size();
if(it.fst > r2) G += it.snd.size();
}
}
if(!(l == 0 and g == 0) and max(l, g) <= N/2) return R;
if(!(L == 0 and G == 0) and max(L, G) <= N/2) return R;
return -R;
}
/*
INT hubDistance(INT N, INT sub) {
ii far = {-1, -1};
FOR(i, 1, N) far = max({getDistance(0, i), i}, far);
vi d1, d2;
int I = far.snd;
far = {-1, -1};
FOR(i, 0, N) {
if(i == I) d1.pb(0);
else d1.pb(getDistance(I, i)), far = max(far, {d1.back(), i});
}
int J = far.snd;
D = far.fst;
FOR(i, 0, N){
if(i == J) d2.pb(0);
else d2.pb(getDistance(J, i));
}
int R = 1e9;
map<int, int> cnt;
FOR(i, 0, N){
int d = (d1[i] + d2[i] - D)/2;
cnt[d1[i]-d]++;
R = min(R, max(d1[i]-d, d2[i]-d));
}
int r2 = D - R;
// amnt < R, = R, > R
int l = 0, e = 0, g = 0;
int L = 0, E = 0, G = 0;
for(auto it : cnt){
if(cnt[R] != 0){
if(it.fst < R) l += it.snd;
if(it.fst == R) e += it.snd;
if(it.fst > R) g += it.snd;
}
if(cnt[r2] != 0){
if(it.fst < r2) L += it.snd;
if(it.fst == r2) E += it.snd;
if(it.fst > r2) G += it.snd;
}
}
if(max(l, max(e, g)) > N/2) R *= -1;
if(max(L, max(E, G)) > N/2 and R >= 0) R *= -1;
return R;
}
*/
Compilation message
towns.cpp: In function 'INT hubDistance(INT, INT)':
towns.cpp:29:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
else dist[i].pb(getDistance(i, j));
^
towns.cpp:29:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
towns.cpp:91:19: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
if(!poss) return -R;
^~
towns.cpp:107:55: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
if(!(l == 0 and g == 0) and max(l, g) <= N/2) return R;
^
towns.cpp:108:55: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
if(!(L == 0 and G == 0) and max(L, G) <= N/2) return R;
^
towns.cpp:109:9: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
return -R;
^~
towns.cpp:46:6: warning: unused variable 'e' [-Wunused-variable]
int e = 0;
^
towns.cpp:24:28: warning: unused parameter 'sub' [-Wunused-parameter]
INT hubDistance(INT N, INT sub) {
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
504 KB |
Output is correct |
| 2 |
Correct |
21 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
32 ms |
620 KB |
Output is correct |
| 5 |
Correct |
25 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
820 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
