oj.uz

Submission #161675

# Submission time Handle Problem Language Result Execution time Memory
161675 2019-11-03T17:17:04 Z Anai timeismoney (balkan11_timeismoney) C++14
100 / 100
 644 ms 760 KB 
//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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 9 ms 632 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 7 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 76 ms 376 KB Output is correct
17 Correct 95 ms 376 KB Output is correct
18 Correct 76 ms 376 KB Output is correct
19 Correct 644 ms 632 KB Output is correct
20 Correct 644 ms 760 KB Output is correct