Submission #230378

#	Time	Username	Problem	Language	Result	Execution time	Memory
230378		qkxwsm	ČVENK (COI15_cvenk)	C++14	60 / 100	1976 ms	472580 KiB

cvenk

#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);
        // cerr << "WTMOO\n";
        // for (pii p : vec)
        // {
        //     cerr << p.fi << ' ' << p.se << endl;
        // }
        FOR(i, 0, SZ(vec) - 1)
        {
            if (i == 0)
            {
                int u = indexof(compress, vec[i]), v = indexof(compress, vec[i + 1]);
                edge[u].PB(v);
                dup[v] = calc(vec[i], vec[i + 1]);
            }
            else
            {
                lch[vec[i]].PB(vec[i + 1]);
            }
            // cerr << vec[i].fi << ',' << vec[i].se << ' ' << vec[i + 1].fi << ',' << vec[i + 1].se << endl;
            // 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)
        {
            if (i == 0)
            {
                int u = indexof(compress, vec[i]), v = indexof(compress, vec[i + 1]);
                edge[u].PB(v);
                dup[v] = calc(vec[i], vec[i + 1]);
            }
            else
            {
                rch[vec[i]].PB(vec[i + 1]);
            }
            // cerr << vec[i].fi << ',' << vec[i].se << ' ' << vec[i + 1].fi << ',' << vec[i + 1].se << endl;
            // 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;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 0 / 40