Submission #161675

#	Time	Username	Problem	Language	Result	Execution time	Memory
161675		Anai	timeismoney (balkan11_timeismoney)	C++14	100 / 100	644 ms	760 KiB

timeismoney

//11860 1203
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

const int N = 205;

using i64 = long long;
using f64 = double;

using pii = pair<int, int>;
using ptx = pair<f64, f64>;

struct Edge {
	int u, v, x, y; };


int far[N];

vector<Edge> partans;
vector<Edge> edgs;
int n, m;
pii ans;


static int get_far(int u) {
	return (far[u] == -1 ? u : (far[u] = get_far(far[u]))); }

static bool join(int a, int b) {
	a = get_far(a);
	b = get_far(b);
	if (a == b)
		return false;
	if (rand() % 2)
		swap(a, b);
	far[a] = b;
	return true; }

static pii solve(i64 a, i64 b) {
	static vector<Edge> select;
	select.clear();

	pii ant(0, 0);
	memset(far, 0xff, sizeof far);
	sort(begin(edgs), end(edgs), [&](const Edge &s, const Edge &t) {
		return make_pair(a * s.x + b * s.y, pii(s.u, s.v)) < make_pair(a * t.x + b * t.y, pii(t.u, t.v)); });

	for (auto e: edgs) {
		if (join(e.u, e.v)) {
			select.push_back(e);
			ant.x+= e.x;
			ant.y+= e.y; } }

	if (1LL * ant.x * ant.y < 1LL * ans.x * ans.y) {
		partans = select;
		ans = ant; }

	return ant; }

static i64 ccw(pii a, pii b, pii c) {
	return i64(a.x - b.x) * (c.y - b.y) - i64(a.y - b.y) * (c.x - b.x); }

static void divide(pii a, pii b) {
	pii mid = solve(a.y - b.y, b.x - a.x);
	if (mid == a || mid == b || a == b)
		return;
	if (ccw(a, b, mid) <= 0)
		return;
	divide(a, mid);
	divide(mid, b); }

int main() {
#ifdef HOME
	freopen("timeismoney.in", "r", stdin);
	freopen("timeismoney.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	srand(time(NULL));
	ans = pii(1e9, 1e9);

	cin >> n >> m;
	edgs.resize(m);
	for (auto &e: edgs)
		cin >> e.u >> e.v >> e.x >> e.y;

	divide(solve(1, 0), solve(0, 1));

	cout << ans.x << ' ' << ans.y << '\n';
	for (auto e: partans)
		cout << e.u << ' ' << e.v << '\n';

	return 0; }

• Subtask 1: 100 / 100