제출 #230374

#제출 시각아이디문제언어결과실행 시간메모리
230374qkxwsmČVENK (COI15_cvenk)C++14
0 / 100
1939 ms461788 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<class T, class U> void ckmin(T &a, U b) { if (a > b) a = b; } template<class T, class U> void ckmax(T &a, U b) { if (a < b) a = b; } #define MP make_pair #define PB push_back #define LB lower_bound #define UB upper_bound #define fi first #define se second #define SZ(x) ((int) (x).size()) #define ALL(x) (x).begin(), (x).end() #define FOR(i, a, b) for (auto i = (a); i < (b); i++) #define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpi; typedef vector<pll> vpl; const int MAXN = 1000013; const ll LLINF = 3e18; #define int long long int N, M; pll arr[MAXN]; ll ans = LLINF; vpl compress; vi edge[MAXN]; ll dup[MAXN]; map<pll, vpl> lch, rch; ll stor[MAXN], depth[MAXN], subtree[MAXN]; int lsb(ll x) { if (x == 0) return 64; return __builtin_ctzll(x); } int indexof(vpl &v, pll p) { return LB(ALL(v), p) - v.begin(); } ll calc(pll a, pll b) { return abs(a.fi - b.fi) + abs(a.se - b.se); } pll parent(pll p) { if (p == MP(0ll, 0ll)) { return p; } int cx = lsb(p.fi), cy = lsb(p.se); if (cx < cy) { return {p.fi - (1ll << cx), p.se}; } else { return {p.fi, p.se - (1ll << cy)}; } } void dfs(int u, int p) { subtree[u] = stor[u]; for (int v : edge[u]) { depth[v] = depth[u] + dup[v]; dfs(v, u); subtree[u] += subtree[v]; } } void solve(int u, int p, ll c) { ckmin(ans, c); for (int v : edge[u]) { solve(v, u, c + (N - 2 * subtree[v]) * dup[v]); } } int32_t main() { cout << fixed << setprecision(12); cerr << fixed << setprecision(4); ios_base::sync_with_stdio(false); cin.tie(0); cin >> N; FOR(i, 0, N) { cin >> arr[i].fi >> arr[i].se; vpl pts; pll p = arr[i]; while(p != MP(0ll, 0ll)) { pts.PB(p); p = parent(p); } pts.PB(p); reverse(ALL(pts)); FOR(j, 1, SZ(pts)) { if (pts[j].se == pts[j - 1].se) { lch[pts[j - 1]].PB(pts[j]); } else { rch[pts[j - 1]].PB(pts[j]); } } compress.insert(compress.end(), ALL(pts)); } sort(ALL(compress)); compress.erase(unique(ALL(compress)), compress.end()); M = SZ(compress); for (auto a : lch) { vpl vec = a.se; sort(ALL(vec)); vec.erase(unique(ALL(vec)), vec.end()); vec.insert(vec.begin(), a.fi); FOR(i, 0, SZ(vec) - 1) { int u = indexof(compress, vec[i]), v = indexof(compress, vec[i + 1]); edge[u].PB(v); dup[v] = calc(vec[i], vec[i + 1]); // cerr << "edge " << u << ' ' << v << ' ' << dup[v] << endl; } } for (auto a : rch) { vpl vec = a.se; sort(ALL(vec)); vec.erase(unique(ALL(vec)), vec.end()); vec.insert(vec.begin(), a.fi); FOR(i, 0, SZ(vec) - 1) { int u = indexof(compress, vec[i]), v = indexof(compress, vec[i + 1]); edge[u].PB(v); dup[v] = calc(vec[i], vec[i + 1]); // cerr << "edge " << u << ' ' << v << ' ' << dup[v] << endl; } } FOR(i, 0, N) { int u = indexof(compress, arr[i]); stor[u]++; // cerr << "incr " << u << endl; } dfs(0, SZ(compress)); ll dis = 0; FOR(i, 0, M) { dis += stor[i] * depth[i]; } solve(0, M, dis); //ok and then we just like do it. // pts.PB({0, 0}); //sort by dfs order. //we need to somehow build the tree. cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...