Submission #43276

#	Time	Username	Problem	Language	Result	Execution time	Memory
43276		aome	timeismoney (balkan11_timeismoney)	C++14	100 / 100	611 ms	944 KiB

timeismoney

#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 / 100