This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
_ _ _______ _ _
| | / / | _____| | | / /
| | / / | | | | / /
| |/ / | |_____ | |/ /
| |\ \ | _____| | |\ \
| | \ \ | | | | \ \
| | \ \ | |_____ | | \ \
|_| \_\ |_______| |_| \_\
*/
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair < ll, int > PLI;
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek
#define fname ""
const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 2e6 + 6;
int n;
bool u[N];
vector < PII > vec;
vector < pair < PII, int > > a;
ll d[N], sz[N], ans = ool;
vector < pair < int, ll > > g[N];
map < PII, int > cnt;
bool cmp(pair < PII, int > a, pair < PII, int > b) {
if (a.F.S != b.F.S) return a.F.S < b.F.S;
return a.F.F < b.F.F;
}
void calc(int v, int par) {
if (u[v]) assert(0);
u[v] = 1;
for (auto it : g[v]) {
int to = it.F;
assert(v != to);
if (to == par) continue;
//cerr << vec[v - 1].F << " " << vec[v - 1].S << " --" << it.S << "--> " << vec[to - 1].F << " " << vec[to - 1].S << "\n";
calc(to, v);
sz[v] += sz[to];
d[v] += d[to] + sz[to];
}
}
void dfs(int v, int par, ll up) {
for (auto it : g[v]) {
int to = it.F;
if (to == par) continue;
ans = min(ans, up + d[to] + min(sz[to], sz(a) - sz[to]) * it.S);
dfs(to, v, up + d[v] - d[to] - sz[to] + (sz(a) - sz[to]) * it.S);
}
}
int main() {
#ifdef krauch
freopen("input.txt", "r", stdin);
#else
//freopen(fname".in", "r", stdin);
//freopen(fname".out", "w", stdout);
#endif
cin >> n;
forn(i, 1, n) {
int x, y;
cin >> x >> y;
cnt[PII(x, y)]++;
vec.eb(x, y);
forn(i, 0, 31) {
if (!((x >> i) & 1) && !(y >> i) & 1) continue;
if ((x >> i) & 1) x -= 1 << i;
if ((y >> i) & 1) y -= 1 << i;
vec.eb(x, y);
}
}
sort(all(vec));
vec.erase(unique(all(vec)), vec.end());
forn(i, 0, sz(vec) - 1) {
a.eb(vec[i], i + 1);
sz[i + 1] = cnt[PII(vec[i].F, vec[i].S)];
if (i && vec[i - 1].F == vec[i].F) {
g[i].eb(i + 1, vec[i].S - vec[i - 1].S);
}
}
sort(all(a), cmp);
forn(i, 1, sz(a) - 1) {
if (a[i - 1].F.S == a[i].F.S) {
g[a[i - 1].S].eb(a[i].S, a[i].F.F - a[i - 1].F.F);
}
}
calc(1, -1);
ans = d[1];
dfs(1, -1, 0);
cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |