Submission #1242178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242178		MateiKing80	timeismoney (balkan11_timeismoney)	C++20	100 / 100	539 ms	704 KiB

timeismoney

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int BULAN = 1000;
const ll inf = 1e15;

struct Edge {
	int u, v, a, b;
};

struct DSU {
	vector<int> tati;
	DSU (int n) {
		tati.resize(n + 1, -1);
	}
	int real(int x) {
		if (tati[x] < 0)
			return x;
		return tati[x] = real(tati[x]);
	}
	bool join(int x, int y) {
		x = real(x);
		y = real(y);
		if (x == y)
			return false;
		if (-tati[x] < -tati[y])
			swap(x, y);
		tati[x] += tati[y];
		tati[y] = x;
		return true;
	}
};

int main() {
	int n, m;
	cin >> n >> m;
	vector<Edge> e;
	for (int i = 0; i < m; i ++) {
		Edge x;
		cin >> x.u >> x.v >> x.a >> x.b;
		e.push_back(x);
	}
	ll bestAns = inf;
	int besta = 0, bestb = 0;
	
	for (int i = 0; i <= BULAN; i ++) {
		sort(e.begin(), e.end(), [&] (Edge a, Edge b) {return 1ll * a.a * BULAN + 1ll * a.b * i < 1ll * b.a * BULAN + 1ll * b.b * i;});
		DSU ds(n);
		int sumA = 0, sumB = 0;
		for (auto j : e) {
			if (ds.join(j.u, j.v)) {
				sumA += j.a;
				sumB += j.b;
			}
		}
		if (1ll * sumA * sumB < bestAns) {
			bestAns = 1ll * sumA * sumB;
			besta = BULAN;
			bestb = i;
		}
	}
	
	for (int i = 0; i <= BULAN; i ++) {
		sort(e.begin(), e.end(), [&] (Edge a, Edge b) {return 1ll * a.b * BULAN + 1ll * a.a * i < 1ll * b.b * BULAN + 1ll * b.a * i;});
		DSU ds(n);
		int sumA = 0, sumB = 0;		
		for (auto j : e) {
			if (ds.join(j.u, j.v)) {
				sumA += j.a;
				sumB += j.b;
			}
		}
		if (1ll * sumA * sumB < bestAns) {
			bestAns = 1ll * sumA * sumB;
			bestb = BULAN;
			besta = i;
		}
	}
	
	sort(e.begin(), e.end(), [&] (Edge a, Edge b) {return 1ll * a.a * besta + 1ll * a.b * bestb < 1ll * b.a * besta + 1ll * b.b * bestb;});
	DSU ds(n);
	int sumA = 0, sumB = 0;
	vector<pair<int, int>> afis;
	for (auto j : e) {
		if (ds.join(j.u, j.v)) {
			sumA += j.a;
			sumB += j.b;
			afis.push_back({j.u, j.v});
		}
	}
	cout << sumA << " " << sumB << '\n';
	for (auto i : afis)
		cout << i.first << " " << i.second << '\n';
}

• Subtask 1: 100 / 100