제출 #986121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986121		beaboss	timeismoney (balkan11_timeismoney)	C++14	5 / 100	2065 ms	14116 KiB

timeismoney

// Source: https://oj.uz/problem/view/balkan11_timeismoney
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }

vector<array<ll, 4> > e;

ll n;

struct DSU {
	vi p;
	DSU(ll sz) : p(sz, -1) {}

	ll get(ll cur) {
		if (p[cur] < 0) return cur;
		else return p[cur] = get(p[cur]);
	}

	bool unite(ll a, ll b) {
		a = get(a);
		b = get(b);
		if (a == b) return false;
		if (-p[a] > -p[b]) swap(a, b);
		p[b] += p[a];
		p[a] = b;
		return true;
	}
};

vpii best;
ll mn = 1e18;
pii pr;
pii solve(ll w1, ll w2) {
	// cout << w1 << w2 << endl;
	assert(w1 >= 0 && w2 >= 0);
	sort(e.begin(), e.end(), [&](array<ll, 4> a, array<ll, 4> b) {
		return w1 * a[2] + w2 * a[3] < w1 * b[2] + w2 * b[3];
	});

	DSU dsu(n);
	vpii sol;
	ll c = 0, t=  0;
	for (auto val: e) {
		if (dsu.unite(val[0], val[1])) {
			sol.pb({val[0], val[1]});
			t += val[2];
			c += val[3];
		}
	}

	if (t * c < mn) {
		best = sol;
		pr = {t, c};
	}
	return {t, c};
}
ll cross(pii a, pii b, pii c) {
	return (b.f - a.f) * (c.s - a.s) - (b.s - a.s) * (c.f - a.f);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll m;
	cin >> n >> m;

	FOR(i, 0, m) {
		ll a, b, c, d;
		cin >> a >> b >> c >> d;
		e.pb({a, b, c, d});
	}

	pii A = solve(1, 0);
	pii B = solve(0, 1);

	// cout << B.f << ' ' << B.s << endl;
	// cout << A.f << ' ' << A.s << endl;


	queue<pair<pii, pii> > q;
	q.push({A, B});

	while (!q.empty()) {
		auto cur = q.front();
		q.pop();

		tie(A, B) = cur;
		// cout << A.f << B
		pii here = solve((B.f - A.f), (A.s - B.s));
		// cout << here.f << ' ' << here.s << endl;
		if (cross(B, A, here) > 0) continue;

		q.push({A, here});
		q.push({here, B});
	}

	cout << pr.f << ' ' << pr.s << endl;
	for (auto val: best) cout << val.f << ' ' << val.s << endl;


}

• Subtask 1: 5 / 100