oj.uz

Submission #986127

# Submission time Handle Problem Language Result Execution time Memory
986127 2024-05-19T19:02:56 Z beaboss timeismoney (balkan11_timeismoney) C++14
100 / 100
 419 ms 988 KB 
// 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};
		mn = t * c;
	}

	return {t, c};
}
ll cross(pii a, pii b, pii c) {
	// cout << a.f 
	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});

	// cout << cross({1, 0}, {0, 1}, {0, 0}) << endl;

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

		tie(A, B) = cur;
		// cout << A.f << B
		pii here = solve((A.s - B.s), (B.f - A.f));
		// 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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 4 ms 988 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 4 ms 488 KB Output is correct
15 Correct 3 ms 348 KB Output is correct
16 Correct 48 ms 348 KB Output is correct
17 Correct 51 ms 344 KB Output is correct
18 Correct 47 ms 344 KB Output is correct
19 Correct 413 ms 988 KB Output is correct
20 Correct 419 ms 988 KB Output is correct