Submission #1265003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265003		Lucpp	timeismoney (balkan11_timeismoney)	C++20	100 / 100	372 ms	712 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)size(x)
#define all(x) (x).begin(), (x).end()

struct Dsu{
	vector<int> par;

	Dsu(int n){
		par.resize(n);
		iota(all(par), 0);
	}

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

	void merg(int u, int v){
		u = find(u), v = find(v);
		if(u == v) return;
		par[u] = v;
	}
};

int main(){
	cin.tie(0)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<tuple<int, int, int, int>> edges;
	for(int i = 0; i < m; i++){
		int u, v, x, y;
		cin >> u >> v >> x >> y;
		edges.emplace_back(u, v, x, y);
	}
	auto calc = [&](ll a, ll b) -> tuple<ll, ll, vector<pair<int, int>>> {
		sort(all(edges), [&](auto e, auto f){
			auto [u1, v1, x1, y1] = e;
			auto [u2, v2, x2, y2] = f;
			ll z1 = a*x1+b*y1;
			ll z2 = a*x2+b*y2;
			if(z1 != z2) return z1 < z2;
			return x1 < x2;
		});
		Dsu dsu(n);
		ll resX = 0, resY = 0;
		vector<pair<int, int>> res;
		for(auto [u, v, x, y] : edges){
			if(dsu.find(u) != dsu.find(v)){
				dsu.merg(u, v);
				resX += x;
				resY += y;
				res.emplace_back(u, v);
			}
		}
		return {resX, resY, res};
	};
	ll ansX = 1e9, ansY = 1e9;
	vector<pair<int, int>> ansEdges;
	auto rec = [&](auto&& self, ll x1, ll y1, ll x2, ll y2) -> void {
		assert(x1 <= x2);
		if(x1 == x2){
			assert(y1 == y2);
			return;
		}
		auto [x, y, e] = calc(y1-y2, x2-x1);
		if(x*y < ansX*ansY) ansX = x, ansY = y, ansEdges = e;
		assert(x < x2);
		if(x == x1) return;
		self(self, x1, y1, x, y);
		self(self, x, y, x2, y2);
	};
	auto [x1, y1, e1] = calc(1, 0);
	auto [x2, y2, e2] = calc(0, 1);
	if(x1*y1 < ansX*ansY) ansX = x1, ansY = y1, ansEdges = e1;
	if(x2*y2 < ansX*ansY) ansX = x2, ansY = y2, ansEdges = e2;
	rec(rec, x1, y1, x2, y2);
	cout << ansX << " " << ansY << "\n";
	for(auto [u, v] : ansEdges){
		cout << u << " " << v << "\n";
	}
}

• Subtask 1: 100 / 100