oj.uz

Submission #986123

# Submission time Handle Problem Language Result Execution time Memory
986123 2024-05-19T18:54:06 Z beaboss timeismoney (balkan11_timeismoney) C++14
45 / 100
 4 ms 992 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};
	}
	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((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
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 992 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Incorrect 1 ms 348 KB Output isn't correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Incorrect 4 ms 992 KB Output isn't correct
20 Incorrect 4 ms 992 KB Output isn't correct