| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 287305 |
2020-08-31T15:13:52 Z |
evpipis |
Towns (IOI15_towns) |
C++11 |
|
31 ms |
896 KB |
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
const int len = 115;
int n, s, a, b, dep[len];
map<ii, int> mym;
map<int, vector<int> > adj;
int ask(int a, int b){
if (a > b)
swap(a, b);
if (mym.count(mp(a, b)))
return mym[mp(a, b)];
return mym[mp(a, b)] = getDistance(a, b);
}
void fix_graph(){
s = 0, a = 0, b = 0;
for (int i = 0; i < n; i++)
if (ask(s, i) > ask(s, a))
a = i;
for (int i = 0; i < n; i++)
if (ask(a, i) > ask(a, b))
b = i;
adj.clear();
for (int i = 0; i < n; i++){
int pos = (ask(a, i)+ask(a, s)-ask(s, i))/2;
adj[pos].pb(i);
dep[i] = (ask(a, i)+ask(s, i)-ask(a, s))/2;
//printf("i = %d, dep = %d, pos = %d\n", i, dep[i], pos);
}
//printf("graph fixed\n");
//printf("s = %d, a = %d, b = %d\n", s, a, b);
}
void find_hubs(int &R, vector<int> &hubs){
int diam = ask(a, b);
R = diam;
hubs.clear();
for (auto &it: adj){
int pos = it.fi;
//printf("pos = %d\n", pos);
//printf("mx = %d\n", max(pos, diam-pos));
if (max(pos, diam-pos) < R)
hubs.clear(), hubs.pb(pos), R = max(pos, diam-pos);
else if (max(pos, diam-pos) == R)
hubs.pb(pos);
}
}
bool check(int a, int b){
return (ask(a, b) < dep[a]+dep[b]);
}
bool check_cent(vector<int> ball){
vector<int> stck;
vector<vector<ii> > cons;
for (int i = 0; i < ball.size(); i++){
int cur = ball[i];
if (stck.empty())
cons.pb(vector<ii>(0));
if (!stck.empty() && !check(stck.back(), cur))
cons.back().pb(mp(stck.back(), cur)), stck.pop_back();
else
stck.pb(cur);
}
if (stck.empty())
return true;
/*printf("now cons:\n");
for (int x = 0; x < cons.size(); x++){
printf("x = %d\n", x);
for (int y = 0; y < cons[x].size(); y++)
printf("(%d, %d) ", cons[x][y].fi, cons[x][y].se);
printf("\n");
}*/
int cnt = stck.size();
for (int i = 0; i < cons.size(); i++){
if (cons[i].empty()) continue;
if (check(cons[i][0].fi, stck.back())){
cnt += cons[i].size();
continue;
}
for (int j = 0; j < cons[i].size(); j++)
if (check(cons[i][j].se, stck.back()))
cnt++;
}
return (cnt <= n/2);
}
int hubDistance(int N, int sub) {
mym.clear(), n = N;
vector<int> hubs;
int R, balanced = 0;
fix_graph();
find_hubs(R, hubs);
auto it = adj.begin();
int lef = 0;
for (auto pos: hubs){
//printf("pos = %d\n", pos);
while ((*it).fi < pos)
lef += (*it).se.size(), it++;
int sz = (*it).se.size();
if (lef <= n/2 && sz <= n/2 && (n-lef-sz) <= n/2)
balanced = 1;
//printf("sz = %d\n", sz);
if (sz > n/2 && check_cent((*it).se))
balanced = 1;
}
if (balanced)
return R;
else
return -R;
}
Compilation message
towns.cpp: In function 'int ask(int, int)':
towns.cpp:16:21: warning: declaration of 'b' shadows a global declaration [-Wshadow]
16 | int ask(int a, int b){
| ^
towns.cpp:12:14: note: shadowed declaration is here
12 | int n, s, a, b, dep[len];
| ^
towns.cpp:16:21: warning: declaration of 'a' shadows a global declaration [-Wshadow]
16 | int ask(int a, int b){
| ^
towns.cpp:12:11: note: shadowed declaration is here
12 | int n, s, a, b, dep[len];
| ^
towns.cpp: In function 'bool check(int, int)':
towns.cpp:64:24: warning: declaration of 'b' shadows a global declaration [-Wshadow]
64 | bool check(int a, int b){
| ^
towns.cpp:12:14: note: shadowed declaration is here
12 | int n, s, a, b, dep[len];
| ^
towns.cpp:64:24: warning: declaration of 'a' shadows a global declaration [-Wshadow]
64 | bool check(int a, int b){
| ^
towns.cpp:12:11: note: shadowed declaration is here
12 | int n, s, a, b, dep[len];
| ^
towns.cpp: In function 'bool check_cent(std::vector<int>)':
towns.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int i = 0; i < ball.size(); i++){
| ~~^~~~~~~~~~~~~
towns.cpp:93:24: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
93 | int cnt = stck.size();
| ~~~~~~~~~^~
towns.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i = 0; i < cons.size(); i++){
| ~~^~~~~~~~~~~~~
towns.cpp:98:33: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
98 | cnt += cons[i].size();
| ^
towns.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (int j = 0; j < cons[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:125:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
125 | lef += (*it).se.size(), it++;
| ^
towns.cpp:127:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
127 | int sz = (*it).se.size();
| ~~~~~~~~~~~~~^~
towns.cpp:110:28: warning: unused parameter 'sub' [-Wunused-parameter]
110 | int hubDistance(int N, int sub) {
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
768 KB |
Output is correct |
| 2 |
Correct |
17 ms |
768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
25 ms |
768 KB |
Output is correct |
| 5 |
Correct |
23 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
384 KB |
Output is correct |
| 2 |
Correct |
17 ms |
896 KB |
Output is correct |
| 3 |
Correct |
22 ms |
896 KB |
Output is correct |
| 4 |
Correct |
24 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
768 KB |
Output is correct |
| 2 |
Correct |
23 ms |
768 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
23 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
384 KB |
Output is correct |
| 2 |
Correct |
27 ms |
768 KB |
Output is correct |
| 3 |
Correct |
31 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
384 KB |
Output is correct |
| 2 |
Correct |
24 ms |
896 KB |
Output is correct |
| 3 |
Correct |
23 ms |
896 KB |
Output is correct |
