| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 304689 |
2020-09-21T17:28:01 Z |
AM1648 |
ČVENK (COI15_cvenk) |
C++17 |
|
931 ms |
26744 KB |
/* be name khoda */
// #define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;
#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif
typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;
#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))
#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl
const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;
#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD
// -----------------------------------------------------------------------
const ll maxn = 200010;
const ll maxalg = 30;
ll n, m, par[maxn], sz[maxn];
pii ver[maxn], tour[maxn];
vi subt[maxn];
map<pii, ll> cnt;
inline ll ht(pii &x) {
return x.F + x.S;
}
pii kth_par(pii x, ll k) {
while (x.F && x.S) {
ll lb1 = x.F & -x.F;
ll lb2 = x.S & -x.S;
if (lb1 < lb2) {
if (lb1 >= k) return {x.F - k, x.S};
else x.F -= lb1, k -= lb1;
} else {
if (lb2 >= k) return {x.F, x.S - k};
else x.S -= lb2, k -= lb2;
}
}
if (x.F >= k) return {x.F - k, x.S};
else if (x.S >= k) return {x.F, x.S - k};
else return {0, 0};
}
bool st_cmp(pii &a, pii &b) {
if (ht(a) < ht(b)) {
pii bb = kth_par(b, ht(b) - ht(a));
return a == bb ? true : a.F < bb.F;
} else {
pii aa = kth_par(a, ht(a) - ht(b));
return aa == b ? false : aa.F < b.F;
}
}
bool a_subt_b(pii &a, pii &b) {
return (ht(a) >= ht(b)) && (kth_par(a, ht(a) - ht(b)) == b);
}
pii lca(pii a, pii b) {
if (ht(a) < ht(b)) swap(a, b);
a = kth_par(a, ht(a) - ht(b));
if (a == b) return a;
forir (i, maxalg) {
pii aa = kth_par(a, 1 << i), bb = kth_par(b, 1 << i);
if (aa != bb) a = aa, b = bb;
}
return kth_par(a, 1);
}
void make_virt_tree() {
sort(ver, ver + n, st_cmp);
m = unique(ver, ver + n) - ver;
fori (i, m - 1) {
ver[m + i] = lca(ver[i], ver[i + 1]);
}
m += m - 1;
sort(ver, ver + m, st_cmp);
m = unique(ver, ver + m) - ver;
forifrom (i, 1, m) {
par[i] = i - 1;
while (par[i] && !a_subt_b(ver[i], ver[par[i]])) par[i] = par[par[i]];
subt[par[i]].eb(i);
}
}
void dfs_sz(ll x) {
sz[x] = cnt[ver[x]];
for (auto y : subt[x]) {
dfs_sz(y);
sz[x] += sz[y];
}
}
ll dfs_cent(ll x) {
for (auto y : subt[x]) if (sz[y] * 2 > n) return dfs_cent(y);
return x;
}
long long sum_dist(ll x) {
long long s = 0;
fori (i, n) {
pii c = lca(tour[i], ver[x]);
s += ht(tour[i]) + ht(ver[x]) - ht(c) * 2;
}
return s;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
fori (i, n) {
ll r, c; cin >> r >> c;
ver[i] = tour[i] = {r, c};
++cnt[{r, c}];
}
make_virt_tree();
dfs_sz(0);
ll cent = dfs_cent(0);
long long ans = sum_dist(cent);
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
4 ms |
4992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
7856 KB |
Output is correct |
| 2 |
Correct |
104 ms |
7928 KB |
Output is correct |
| 3 |
Correct |
40 ms |
7168 KB |
Output is correct |
| 4 |
Correct |
39 ms |
7160 KB |
Output is correct |
| 5 |
Correct |
61 ms |
7416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
925 ms |
26744 KB |
Output is correct |
| 2 |
Correct |
931 ms |
26744 KB |
Output is correct |
| 3 |
Correct |
290 ms |
23800 KB |
Output is correct |
| 4 |
Correct |
288 ms |
21240 KB |
Output is correct |
| 5 |
Correct |
296 ms |
20856 KB |
Output is correct |
