| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 623980 |
2022-08-07T06:20:28 Z |
8e7 |
Towns (IOI15_towns) |
C++17 |
|
16 ms |
940 KB |
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 155
#define pii pair<int, int>
#define ff first
#define ss second
#include "towns.h"
int n;
int save[maxn][maxn];
bool done[maxn][maxn];
int query(int u, int v) {
if (u == v || u >= n || v >= n) return 0;
if (done[u][v]) return save[u][v];
save[u][v] = save[v][u] = getDistance(u, v);
done[u][v] = done[v][u] = 1;
return save[u][v];
}
bool check[2*maxn];
vector<int> eq[2*maxn], dif[2*maxn];
int hubDistance(int N, int sub) {
n = N;
for (int i = 0;i <= n;i++) {
for (int j = 0;j <= n;j++) done[i][j] = 0;
}
for (int i = 0;i <= 2*n;i++) {
eq[i].clear();
dif[i].clear();
check[i] = 0;
}
vector<int> da, db, l(n), w(n), ws;
int b = 0, ma = 0;
for (int i = 0;i < n;i++) {
da.push_back(query(0, i));
if (da.back() > ma) {
ma = da.back();
b = i;
}
}
int len = ma;
for (int i = 0;i < n;i++) {
db.push_back(query(b, i));
ma = max(ma, db.back());
}
//debug(ma);
int R = 1<<30;
for (int i = 0;i < n;i++) {
l[i] = (da[i] + db[i] - len) / 2;
w[i] = db[i] - l[i];
//debug(l[i], w[i]);
ws.push_back(w[i]);
R = min(R, max(w[i], ma - w[i]));
}
sort(ws.begin(), ws.end());
ws.resize(int(unique(ws.begin(), ws.end()) - ws.begin()));
int siz = ws.size();
vector<vector<int> > col(siz, vector<int>());
vector<int> pref(siz, 0), suf(siz, 0);
for (int i = 0;i < n;i++) {
int ind = lower_bound(ws.begin(), ws.end(), w[i]) - ws.begin();
col[ind].push_back(i);
debug(i, ind);
}
for (int i = 0;i < siz;i++) pref[i] = col[i].size() + (i ? pref[i-1] : 0);
for (int i = siz-1;i >= 0;i--) suf[i] = col[i].size() + (i < siz-1 ? suf[i+1] : 0);
vector<int> vec, tmp;
for (int i = 0;i < siz;i++) {
int v = max(ws[i], ma - ws[i]);
if (v == R) {
if ((i == 0 || pref[i-1] <= n/2) && (i == siz-1 || suf[i+1] <= n/2) && col[i].size() <= n/2) {
return R;
} else if (col[i].size() > n/2) {
vec = col[i];
for (int j = 0;j < n - col[i].size();j++) vec.push_back(n+j);
break;
}
}
}
if (vec.size() == 0) return -R;
tmp = vec;
//pary(vec.begin(), vec.end());
auto same = [&] (int i, int j) {
int v = query(i, j);
if (v == 0) return 0;
int d = l[i] + l[j] - v;
//debug("same", i, j, d ? 1 : 0);
return d ? 1 : 0;
};
//pary(vec.begin(), vec.end());
int surv = 0, hp = 0;
for (int i:vec) {
if (hp == 0) surv = i, hp = 1;
else if (same(surv, i)) {
eq[surv].push_back(i);
hp++;
} else {
dif[surv].push_back(i);
hp--;
}
}
if (hp == 0) return R;
int good = 1, bad = 0;
for (int i:eq[surv]) good++, check[i] = 1;
for (int i:dif[surv]) bad++, check[i] = 1;
check[surv] = 1;
for (int i:vec) {
if (check[i]) continue;
if (i == surv || same(surv, i)) {
good++;
for (int j:eq[i]) good++, check[j] = 1;
for (int j:dif[i]) bad++, check[j] = 1;
} else {
bad++;
for (int j:eq[i]) bad++, check[j] = 1;
}
if (good > n/2) return -R;
if (bad > n/2) return R;
}
if (good > n/2) return -R;
else return R;
}
/*
1 1
6
0 20 12 12 12 12
20 0 12 12 12 12
12 12 0 2 2 2
12 12 2 0 2 2
12 12 2 2 0 2
12 12 2 2 2 0
*/
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:71:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
71 | int siz = ws.size();
| ~~~~~~~^~
towns.cpp:75:53: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
75 | int ind = lower_bound(ws.begin(), ws.end(), w[i]) - ws.begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
towns.cpp:77:3: note: in expansion of macro 'debug'
77 | debug(i, ind);
| ^~~~~
towns.cpp:79:54: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
79 | for (int i = 0;i < siz;i++) pref[i] = col[i].size() + (i ? pref[i-1] : 0);
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
towns.cpp:80:56: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
80 | for (int i = siz-1;i >= 0;i--) suf[i] = col[i].size() + (i < siz-1 ? suf[i+1] : 0);
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
towns.cpp:86:89: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
86 | if ((i == 0 || pref[i-1] <= n/2) && (i == siz-1 || suf[i+1] <= n/2) && col[i].size() <= n/2) {
| ~~~~~~~~~~~~~~^~~~~~
towns.cpp:88:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
88 | } else if (col[i].size() > n/2) {
| ~~~~~~~~~~~~~~^~~~~
towns.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int j = 0;j < n - col[i].size();j++) vec.push_back(n+j);
| ~~^~~~~~~~~~~~~~~~~~~
towns.cpp:35:28: warning: unused parameter 'sub' [-Wunused-parameter]
35 | int hubDistance(int N, int sub) {
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
340 KB |
Output is correct |
| 2 |
Correct |
15 ms |
464 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
16 ms |
340 KB |
Output is correct |
| 5 |
Correct |
13 ms |
452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
340 KB |
Output is correct |
| 2 |
Correct |
10 ms |
340 KB |
Output is correct |
| 3 |
Correct |
13 ms |
340 KB |
Output is correct |
| 4 |
Correct |
13 ms |
452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
460 KB |
Output is correct |
| 2 |
Correct |
13 ms |
448 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
14 ms |
456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
464 KB |
Output is correct |
| 2 |
Correct |
13 ms |
340 KB |
Output is correct |
| 3 |
Correct |
14 ms |
456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
468 KB |
Output is correct |
| 2 |
Correct |
13 ms |
340 KB |
Output is correct |
| 3 |
Correct |
14 ms |
940 KB |
Output is correct |
