oj.uz

Submission #230380

# Submission time Handle Problem Language Result Execution time Memory
230380 2020-05-10T00:43:21 Z qkxwsm ČVENK (COI15_cvenk) C++14
100 / 100
 1945 ms 295496 KB 
#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 = 3200013;
const ll LLINF = 3e18;

int N, M;
pll arr[MAXN];
ll ans = LLINF;
vpl compress;
vi edge[MAXN];
ll dup[MAXN];
ll stor[MAXN], depth[MAXN], subtree[MAXN];
map<ll, vl> xs, ys;

int lsb(ll x)
{
    if (x == 0) return 33;
    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);
    compress.PB({0, 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);
        }
        compress.insert(compress.end(), ALL(pts));
    }
    sort(ALL(compress));
    compress.erase(unique(ALL(compress)), compress.end());
    M = SZ(compress);
    FOR(i, 0, M)
    {
        pll p = compress[i];
        xs[p.fi].PB(p.se);
        ys[p.se].PB(p.fi);
    }
    for (auto a : xs)
    {
        int d = lsb(a.fi);
        vl vec = a.se;
        sort(ALL(vec));
        vec.erase(unique(ALL(vec)), vec.end());
        // cerr << "x = " << a.fi << endl;
        // vec.insert(vec.begin(), a.fi);
        FOR(i, 0, SZ(vec) - 1)
        {
            ll s = vec[i], t = vec[i + 1];
            if (t - s >= (1ll << d)) continue;
            // cerr << s << " -> " << t << endl;
            int u = indexof(compress, MP(a.fi, s)), v = indexof(compress, MP(a.fi, t));
            edge[u].PB(v);
            // cerr << u << ' ' << v << ' ' << t - s << endl;
            dup[v] = t - s;
        }
    }
    for (auto a : ys)
    {
        int d = lsb(a.fi);
        vl vec = a.se;
        sort(ALL(vec));
        vec.erase(unique(ALL(vec)), vec.end());
        // cerr << "y = " << a.fi << endl;
        // vec.insert(vec.begin(), a.fi);
        FOR(i, 0, SZ(vec) - 1)
        {
            ll s = vec[i], t = vec[i + 1];
            if (t - s >= (1ll << d)) continue;
            // cerr << s << " -> " << t << endl;
            int u = indexof(compress, MP(s, a.fi)), v = indexof(compress, MP(t, a.fi));
            edge[u].PB(v);
            // cerr << u << ' ' << v << ' ' << t - s << endl;
            dup[v] = t - s;
        }
    }
    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;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 75512 KB Output is correct
2 Correct 49 ms 75520 KB Output is correct
3 Correct 49 ms 75520 KB Output is correct
4 Correct 49 ms 75384 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 75896 KB Output is correct
2 Correct 49 ms 75768 KB Output is correct
3 Correct 49 ms 75768 KB Output is correct
4 Correct 49 ms 75768 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 90056 KB Output is correct
2 Correct 160 ms 88128 KB Output is correct
3 Correct 108 ms 83156 KB Output is correct
4 Correct 105 ms 83776 KB Output is correct
5 Correct 117 ms 83452 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1926 ms 293928 KB Output is correct
2 Correct 1945 ms 295496 KB Output is correct
3 Correct 782 ms 253452 KB Output is correct
4 Correct 829 ms 240388 KB Output is correct
5 Correct 842 ms 243664 KB Output is correct