oj.uz

Submission #43276

# Submission time Handle Problem Language Result Execution time Memory
43276 2018-03-12T15:41:14 Z aome timeismoney (balkan11_timeismoney) C++14
100 / 100
 611 ms 944 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 205;

struct Edge {
	int u, v, c, t;

	Edge (int u, int v, int c, int t) :
		u(u), v(v), c(c), t(t) {}
};

typedef pair<int, int> ii;

int n, m;
int par[N];
vector<Edge> edges;
ii res = ii(1e9, 1e9);
vector<ii> vres, buf;

int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }

bool join(int u, int v) {
	u = find(u), v = find(v), par[u] = v; return u != v;
}

ii get(int c1, int c2) {
	sort(edges.begin(), edges.end(), [&] (Edge x, Edge y) {
		return 1LL * x.c * c1 + 1LL * x.t * c2 < 1LL * y.c * c1 + 1LL * y.t * c2; 
	});
	ii ret = ii(0, 0); buf.clear();
	for (int i = 0; i < n; ++i) par[i] = i;
	for (auto i : edges) {
		if (join(i.u, i.v)) {
			ret.first += i.c, ret.second += i.t;
			buf.push_back(ii(i.u, i.v));
		}
	}
	return ret;
}

bool ccw(ii x, ii y, ii z) {
	return 1LL * (y.first - x.first) * (z.second - x.second) - 1LL * (y.second - x.second) * (z.first - x.first) > 0;
}

void calc(ii x) {
	if (1LL * res.first * res.second > 1LL * x.first * x.second) {
		res = x, vres = buf;
	}
}

void solve(ii l, ii r) {
	ii mid = get(l.second - r.second, r.first - l.first);
	if (ccw(mid, r, l)) {
		calc(mid), solve(l, mid), solve(mid, r);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v, c, t; cin >> u >> v >> c >> t;
		edges.push_back(Edge(u, v, c, t));
	}
	ii l = get(1, 0); calc(l);
	ii r = get(0, 1); calc(r);
	solve(l, r);
	cout << res.first << ' ' << res.second << '\n';
	for (auto i : vres) cout << i.first << ' ' << i.second << '\n';
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 7 ms 920 KB Output is correct
9 Correct 1 ms 920 KB Output is correct
10 Correct 2 ms 920 KB Output is correct
11 Correct 1 ms 920 KB Output is correct
12 Correct 2 ms 920 KB Output is correct
13 Correct 2 ms 920 KB Output is correct
14 Correct 7 ms 920 KB Output is correct
15 Correct 5 ms 920 KB Output is correct
16 Correct 75 ms 920 KB Output is correct
17 Correct 107 ms 920 KB Output is correct
18 Correct 75 ms 920 KB Output is correct
19 Correct 611 ms 944 KB Output is correct
20 Correct 602 ms 944 KB Output is correct