| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 538654 |
2022-03-17T11:39:46 Z |
NachoLibre |
Towns (IOI15_towns) |
C++17 |
|
27 ms |
1068 KB |
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define vint vector<int>
using namespace std;
#ifndef x
#include "towns.h"
#else
vector<vint > formt(int m, vint v) {
vector<vint > x;
for(int i = 0; i < sz(v); ++i) {
if(sz(x) == 0 || sz(x.back()) == m) x.push_back({});
x.back().push_back(v[i]);
}
return x;
}
const int N = 102;
vector<array<int, 2> > v[N];
int dfsDist(int x, int y, int w = 0, int d = 0) {
if(x == y) return d;
for(auto z : v[x]) {
if(z[0] == w) continue;
int t = dfsDist(z[0], y, x, d + z[1]);
if(t) return t;
}
return 0;
}
vector<vector<int> > distArch;
int getDistance(int x, int y) {
if(0) return dfsDist(x, y);
else return distArch[x][y];
}
#endif
map<array<int, 2>, int> ma;
int dist(int x, int y) {
if(x == y) return 0;
if(x > y) swap(x, y);
if(!ma[{x, y}]) {
ma[{x, y}] = getDistance(x, y);
}
return ma[{x, y}];
}
int s;
int globz;
bool sameComponent(int x, int y) {
return dist(s, x) + dist(s, y) - dist(x, y) >> 1 > globz;
}
int majC(vint v) {
int cnt = 0;
vint lst, bckt;
for(int x : v) {
if(!sz(lst) || !sameComponent(x, lst.back())) {
lst.push_back(x);
if(sz(bckt)) {
lst.push_back(bckt.back());
bckt.pop_back();
}
} else {
bckt.push_back(x);
}
}
int t = lst.back();
while(sz(lst)) {
if(sameComponent(t, lst.back())) {
if(sz(lst) == 1) {
bckt.push_back(lst.back());
lst.pop_back();
} else {
lst.pop_back();
cnt += 1;
lst.pop_back();
}
} else {
if(!sz(bckt)) return 0;
bckt.pop_back();
cnt += 1;
lst.pop_back();
}
}
if(!sz(bckt)) return 0;
return cnt + sz(bckt);
}
int hubDistance(int n, int sub) {
// if(sub > 2) assert(0);
ma.clear();
for(int i = 0, mx = 0; i < n; ++i) {
if(dist(0, i) > mx) {
mx = dist(0, i);
s = i;
}
}
// cout << "[s]: " << s << "\n";
int dm = 0;
for(int i = 0; i < n; ++i) {
dm = max(dm, dist(s, i));
}
vector<array<int, 2> > ytf;
for(int i = 1; i < n; ++i) {
if(i == s) continue;
int al = dist(s, i) + dist(s, 0) - dist(0, i) >> 1;
ytf.push_back({al, i});
}
vector<vector<int> > v;
sort(all(ytf));
int lmx = 0, rmn = 0;
for(int i = 0; i < sz(ytf); ++i) {
if(!i || ytf[i - 1][0] < ytf[i][0]) {
v.push_back({});
v.back().push_back(ytf[i][0]);
// cout << "\n" << ytf[i][0] << " -> ";
if(ytf[i][0] <= dm / 2) lmx = ytf[i][0];
else if(!rmn) rmn = ytf[i][0];
}
v.back().push_back(ytf[i][1]);
// cout << ytf[i][1] << " ";
}
if(!lmx) lmx = rmn;
else if(!rmn) rmn = lmx;
else if(dm - lmx < rmn) rmn = lmx;
else if(dm - lmx > rmn) lmx = rmn;
assert(lmx <= rmn);
int dr = -max(lmx, dm - lmx);
vint ftl(sz(v)), ftr(sz(v));
if(sz(v) > 1) {
ftl[1] = 1;
ftr[sz(v) - 2] = 1;
}
for(int i = 1; i < sz(v); ++i) {
ftl[i] += ftl[i - 1] + sz(v[i - 1]) - 1;
}
for(int i = sz(v) - 2; i >= 0; --i) {
ftr[i] += ftr[i + 1] + sz(v[i + 1]) - 1;
}
// cout << lmx << " " << rmn << endl;
for(int i = 0; i < sz(v); ++i) {
// cout << v[i][0] << endl;
if(v[i][0] == lmx || v[i][0] == rmn) {
// cout << ftl[i] << ", " << ftr[i] << endl;
if(ftl[i] > n / 2 || ftr[i] > n / 2) {
continue;
}
globz = v[i][0];
vector<int> t;
for(int j = 1; j < sz(v[i]); ++j) {
t.push_back(v[i][j]);
}
int x = majC(t);
if(x <= n / 2) dr = abs(dr);
}
}
return dr;
}
#ifdef x
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int sub, n;
sub = 1;
n = 11;
distArch = formt(n, vint{
0, 17, 18, 20, 17, 12, 20, 16, 23, 20, 11,
17, 0, 23, 25, 22, 17, 25, 21, 28, 25, 16,
18, 23, 0, 12, 21, 16, 24, 20, 27, 24, 17,
20, 25, 12, 0, 23, 18, 26, 22, 29, 26, 19,
17, 22, 21, 23, 0, 9, 21, 17, 26, 23, 16,
12, 17, 16, 18, 9, 0, 16, 12, 21, 18, 11,
20, 25, 24, 26, 21, 16, 0, 10, 29, 26, 19,
16, 21, 20, 22, 17, 12, 10, 0, 25, 22, 15,
23, 28, 27, 29, 26, 21, 29, 25, 0, 21, 22,
20, 25, 24, 26, 23, 18, 26, 22, 21, 0, 19,
11, 16, 17, 19, 16, 11, 19, 15, 22, 19, 0 });
cout << hubDistance(n, sub) << endl;
return 0;
}
#endif
Compilation message
towns.cpp: In function 'bool sameComponent(int, int)':
towns.cpp:52:33: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
52 | return dist(s, x) + dist(s, y) - dist(x, y) >> 1 > globz;
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:111:36: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
111 | int al = dist(s, i) + dist(s, 0) - dist(0, i) >> 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:91:28: warning: unused parameter 'sub' [-Wunused-parameter]
91 | int hubDistance(int n, int sub) {
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
368 KB |
Output is correct |
| 2 |
Correct |
11 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
17 ms |
372 KB |
Output is correct |
| 5 |
Correct |
18 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
340 KB |
Output is correct |
| 2 |
Correct |
13 ms |
380 KB |
Output is correct |
| 3 |
Correct |
24 ms |
368 KB |
Output is correct |
| 4 |
Correct |
27 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
784 KB |
Output is correct |
| 2 |
Correct |
26 ms |
864 KB |
Output is correct |
| 3 |
Correct |
1 ms |
300 KB |
Output is correct |
| 4 |
Correct |
24 ms |
868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
1068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
724 KB |
Output is correct |
| 2 |
Correct |
18 ms |
864 KB |
Output is correct |
| 3 |
Correct |
19 ms |
868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
680 KB |
Output is correct |
| 2 |
Correct |
19 ms |
852 KB |
Output is correct |
| 3 |
Correct |
17 ms |
908 KB |
Output is correct |
