oj.uz

답안 #161669

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
161669 2019-11-03T16:29:43 Z Anai 시간이 돈 (balkan11_timeismoney) C++14
55 / 100
 2000 ms 504 KB 
#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 void divide(pii a, pii b) {
	pii mid = solve(b.x - a.x, a.y - b.y);
	if (mid == a || mid == b || a == b)
		return;
	if (!( 1.0L * mid.x * (b.y - a.y) / (a.x - b.x)  <= mid.y  ))
		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
55.0 / 100.0

# 결과 실행 시간 메모리 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 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Incorrect 2 ms 376 KB Output isn't correct
12 Execution timed out 2041 ms 376 KB Time limit exceeded
13 Incorrect 2 ms 376 KB Output isn't correct
14 Incorrect 2 ms 380 KB Output isn't correct
15 Correct 2 ms 376 KB Output is correct
16 Incorrect 3 ms 376 KB Output isn't correct
17 Execution timed out 2058 ms 376 KB Time limit exceeded
18 Execution timed out 2061 ms 376 KB Time limit exceeded
19 Incorrect 10 ms 504 KB Output isn't correct
20 Incorrect 10 ms 504 KB Output isn't correct