oj.uz

Submission #161666

# Submission time Handle Problem Language Result Execution time Memory
161666 2019-11-03T16:22:45 Z Anai timeismoney (balkan11_timeismoney) C++14
0 / 100
 19 ms 632 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 (!(a.x <= mid.x && mid.x <= b.x))
		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';
	cerr << ans.x * ans.y << endl;

	return 0; }

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Extra information in the output file
2 Incorrect 2 ms 376 KB Extra information in the output file
3 Incorrect 2 ms 252 KB Extra information in the output file
4 Incorrect 2 ms 376 KB Extra information in the output file
5 Incorrect 2 ms 376 KB Extra information in the output file
6 Incorrect 9 ms 376 KB Extra information in the output file
7 Incorrect 3 ms 376 KB Extra information in the output file
8 Incorrect 19 ms 632 KB Extra information in the output file
9 Incorrect 2 ms 376 KB Extra information in the output file
10 Incorrect 2 ms 376 KB Extra information in the output file
11 Incorrect 2 ms 376 KB Output isn't correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 Incorrect 2 ms 376 KB Output isn't correct
14 Incorrect 3 ms 376 KB Output isn't correct
15 Incorrect 2 ms 376 KB Extra information in the output file
16 Incorrect 4 ms 376 KB Output isn't correct
17 Incorrect 4 ms 376 KB Output isn't correct
18 Incorrect 4 ms 504 KB Output isn't correct
19 Incorrect 12 ms 632 KB Output isn't correct
20 Incorrect 12 ms 632 KB Output isn't correct