| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 790250 |
2023-07-22T13:13:53 Z |
ymm |
Towns (IOI15_towns) |
C++17 |
|
13 ms |
852 KB |
#include "towns.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;
const int N = 120;
int dis0[N], disa[N];//, disb[N];
int dis[N][N];
int cnt;
namespace dsu {
int par[N];
int sz[N];
void init() {
fill(par, par+N, -1);
fill(sz, sz+N, 1);
}
int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
void unite(int v, int u) {
//v = rt(v);
//u = rt(u);
//if (sz[v] < sz[u])
// swap(v, u);
sz[v] += sz[u];
par[u] = v;
}
}
int get(int i, int j)
{
if (i == j)
return 0;
if (i > j)
swap(i, j);
if (!dis[i][j]) {
++cnt;
dis[i][j] = getDistance(i, j);
}
return dis[i][j];
}
int get2(int a, int v, int b)
{
return (get(a, v) + get(a, b) - get(v, b))/2;
}
int find_hub(int a, int b, int n, int r)
{
if (get(a, b) == r*2)
return r;
bool x = 0, y = 0;
vector<int> X, Y;
Loop (i,0,n) {
if (get2(a, i, 0) == r)
x = 1;
if (get2(a, i, 0) == get(a, b) - r)
y = 1;
int x = get2(a, i, 0);
int y = get(a, b) - x;
(x < y? Y: X).push_back(i);
}
if (!x)
return get(a, b) - r;
if (!y)
return r;
if (X.size()*2 > n)
return r;
if (X.size()*2 == n)
return -1;
return get(a, b) - r;
}
int hubDistance(int n, int sub) {
memset(dis, 0, sizeof(dis));
cnt = 0;
Loop (i,0,n)
dis0[i] = get(0, i);
int a = max_element(dis0, dis0+n) - dis0;
Loop (i,0,n)
disa[i] = get(a, i);
int b = max_element(disa, disa+n) - disa;
//Loop (i,0,n)
// disb[i] = get(b, i);
int ans = 1e9;
Loop (i,0,n) {
int x = get2(a, i, 0);
int y = disa[b] - x;
ans = min(ans, max(x, y));
}
int v = find_hub(a, b, n, ans);
if (v == -1)
return ans;
vector<int> L, M, R;
Loop (i,0,n) {
(get2(a, i, 0) < v? L:
get2(a, i, 0) > v? R:
M).push_back(i);
}
if (L.size()*2 > n || R.size()*2 > n)
return -ans;
if (M.size()*2 <= n)
return ans;
auto same = [&](int i, int j) {
return get2(i, a, 0) + get2(j, a, 0) != get(i, j);
};
vector<int> M1, M2, M2h;
for (int i = 0; i < M.size(); i += 2) {
if (i+1 == M.size()) {
M2.push_back(M[i]);
} else if (same(M[i], M[i+1])) {
M2.push_back(M[i]);
M2.push_back(M[i+1]);
} else {
M1.push_back(M[i]);
M1.push_back(M[i+1]);
}
}
int x = -1, cnt = 0;
for (int i = 0; i < M2.size(); i += 2) {
int z = M2[i];
if (cnt == 0 || same(x, z)) {
x = z;
++cnt;
} else {
--cnt;
}
}
if (cnt == 0)
return ans;
cnt = 0;
for (int i = 0; i < M2.size(); i += 2) {
if (same(M2[i], x)) {
++cnt;
if (i+1 < M2.size())
++cnt;
}
}
if (cnt*2 <= M2.size())
return ans;
for (int y : M1)
cnt += same(x, y);
if (cnt*2 <= n)
return ans;
return -ans;
}
Compilation message
towns.cpp: In function 'int find_hub(int, int, int, int)':
towns.cpp:58:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
58 | if (get2(a, i, 0) == r)
| ^
towns.cpp:60:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
60 | if (get2(a, i, 0) == get(a, b) - r)
| ^
towns.cpp:62:7: warning: declaration of 'x' shadows a previous local [-Wshadow]
62 | int x = get2(a, i, 0);
| ^
towns.cpp:55:7: note: shadowed declaration is here
55 | bool x = 0, y = 0;
| ^
towns.cpp:62:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
62 | int x = get2(a, i, 0);
| ^
towns.cpp:63:7: warning: declaration of 'y' shadows a previous local [-Wshadow]
63 | int y = get(a, b) - x;
| ^
towns.cpp:55:14: note: shadowed declaration is here
55 | bool x = 0, y = 0;
| ^
towns.cpp:64:27: warning: conversion from 'll' {aka 'long long int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
64 | (x < y? Y: X).push_back(i);
| ^
towns.cpp:70:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | if (X.size()*2 > n)
| ~~~~~~~~~~~^~~
towns.cpp:72:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | if (X.size()*2 == n)
| ~~~~~~~~~~~^~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:81:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
81 | dis0[i] = get(0, i);
| ^
towns.cpp:82:36: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
82 | int a = max_element(dis0, dis0+n) - dis0;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:84:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
84 | disa[i] = get(a, i);
| ^
towns.cpp:85:36: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
85 | int b = max_element(disa, disa+n) - disa;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:90:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
90 | int x = get2(a, i, 0);
| ^
towns.cpp:99:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
99 | (get2(a, i, 0) < v? L:
| ^
towns.cpp:100:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
100 | get2(a, i, 0) > v? R:
| ^
towns.cpp:101:36: warning: conversion from 'll' {aka 'long long int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
101 | M).push_back(i);
| ^
towns.cpp:103:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
103 | if (L.size()*2 > n || R.size()*2 > n)
| ~~~~~~~~~~~^~~
towns.cpp:103:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
103 | if (L.size()*2 > n || R.size()*2 > n)
| ~~~~~~~~~~~^~~
towns.cpp:105:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
105 | if (M.size()*2 <= n)
| ~~~~~~~~~~~^~~~
towns.cpp:111:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < M.size(); i += 2) {
| ~~^~~~~~~~~~
towns.cpp:112:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | if (i+1 == M.size()) {
| ~~~~^~~~~~~~~~~
towns.cpp:122:14: warning: declaration of 'cnt' shadows a global declaration [-Wshadow]
122 | int x = -1, cnt = 0;
| ^~~
towns.cpp:13:5: note: shadowed declaration is here
13 | int cnt;
| ^~~
towns.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for (int i = 0; i < M2.size(); i += 2) {
| ~~^~~~~~~~~~~
towns.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (int i = 0; i < M2.size(); i += 2) {
| ~~^~~~~~~~~~~
towns.cpp:138:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | if (i+1 < M2.size())
| ~~~~^~~~~~~~~~~
towns.cpp:142:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | if (cnt*2 <= M2.size())
| ~~~~~~^~~~~~~~~~~~
towns.cpp:77:28: warning: unused parameter 'sub' [-Wunused-parameter]
77 | int hubDistance(int n, int sub) {
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
408 KB |
Output is correct |
| 2 |
Correct |
9 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
12 ms |
404 KB |
Output is correct |
| 5 |
Correct |
13 ms |
404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
408 KB |
Output is correct |
| 2 |
Correct |
9 ms |
404 KB |
Output is correct |
| 3 |
Correct |
12 ms |
404 KB |
Output is correct |
| 4 |
Correct |
12 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
340 KB |
Output is correct |
| 2 |
Correct |
12 ms |
404 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
13 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
340 KB |
Output is correct |
| 2 |
Correct |
13 ms |
400 KB |
Output is correct |
| 3 |
Correct |
12 ms |
412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
340 KB |
Output is correct |
| 2 |
Correct |
12 ms |
852 KB |
Output is correct |
| 3 |
Correct |
13 ms |
852 KB |
Output is correct |
