Submission #348707

#	Time	Username	Problem	Language	Result	Execution time	Memory
348707		cheissmart	시간이 돈 (balkan11_timeismoney)	C++14	100 / 100	1415 ms	1408 KiB

timeismoney

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

struct Point {
	int T, C;
	bool operator == (const Point t) {
		return T == t.T && C == t.C;
	}
};

signed main()
{
	IO_OP;

	int n, m;
	cin >> n >> m;
	vi u(m), v(m), t(m), c(m), take(m);
	for(int i = 0; i < m; i++)
		cin >> u[i] >> v[i] >> t[i] >> c[i];
	Point best = {INF, INF};
	auto mst = [&] (int a, int b) -> Point{
		vi take_tmp(m);
		V<array<ll, 2>> edges;
		for(int i = 0; i < m; i++)
			edges.PB({(ll) a * t[i] + (ll) b * c[i], i});
		sort(ALL(edges));
		vi p(n);
		iota(ALL(p), 0);
		function<int(int)> find = [&](int u) {
			return u == p[u] ? u : p[u] = find(p[u]);
		};
		Point res = {0, 0};
		for(auto edge:edges) {
			int x = find(u[edge[1]]), y = find(v[edge[1]]);
			if(x != y) {
				p[x] = y;
				res.T += t[edge[1]], res.C += c[edge[1]];
				take_tmp[edge[1]] = 1;
			}
		}
		if((ll) res.T * res.C < (ll) best.T * best.C) {
			take = take_tmp;
			best = res;
		}
		return res;
	};

	function<void(Point, Point)> recurse = [&] (Point A, Point B) {
		Point C = mst(A.C - B.C, B.T - A.T);
		if((ll) (A.T - C.T) * (A.C - B.C) == (ll) (A.C - C.C) * (A.T - B.T)) // ABC are colinear
			return;
		recurse(A, C);
		recurse(C, B);
	};

	Point A = mst(1, 0), B = mst(0, 1);
	recurse(A, B);

	cout << best.T << " " << best.C << '\n';
	for(int i = 0; i < m; i++) if(take[i])
		cout << u[i] << " " << v[i] << '\n';
}

• Subtask 1: 100 / 100