Submission #40015

#	Time	Username	Problem	Language	Result	Execution time	Memory
40015		krauch	ČVENK (COI15_cvenk)	C++14	100 / 100	1879 ms	374612 KiB

cvenk

/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#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 = 5e6 + 6;

int 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) {
    for (auto it : g[v]) {
        int to = it.F;
        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] * it.S;
    }
}

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[v] - sz[to] * it.S + min(sz[to], n - sz[to]) * it.S);
        dfs(to, v, up + d[v] - d[to] - sz[to] * it.S + (n - 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) {
            bool ok = 0;
            forn(j, 0, 31) {
                if (!vec[i].S || ((vec[i].S >> j) & 1)) ok = 1;
                if (((vec[i].F >> j) & 1) || ((vec[i].S >> j) & 1)) break;
            }
            if (ok) 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) {
            bool ok = 0;
            forn(j, 0, 31) {
                if (!a[i].F.F || ((a[i].F.F >> j) & 1)) ok = 1;
                if (((a[i].F.F >> j) & 1) || ((a[i].F.S >> j) & 1)) break;
            }
            if (ok) 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;
}

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