Submission #1312603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312603		vlomaczk	timeismoney (balkan11_timeismoney)	C++20	100 / 100	294 ms	1088 KiB

timeismoney

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct Edge {
	ll a,b,t,c;
};
vector<Edge> edges;

vector<ll> rep, sajz;
vector<pair<ll, ll>> res;
ll inf = 1e9;
pair<ll, ll> best = {inf,inf};

ll Find(ll v) {
	return (rep[v]==v ? v : rep[v] = Find(rep[v]));
}

bool Union(ll a, ll b) {
	a=Find(a); b=Find(b);
	if(a==b) return 0;
	rep[a] = b;
	return 1;
}

ll n, m;

pair<ll, ll> mst(ll a, ll b) {
	rep.assign(n+1, 0);
	sajz.assign(n+1, 1);
	for(ll i=1; i<=n; ++i) rep[i] = i;
	pair<ll, ll> wynik = {0,0};
	sort(edges.begin(), edges.end(), [&](Edge x, Edge y){
		return x.t*a + x.c*b < y.t*a + y.c*b;
	});
	vector<pair<ll, ll>> kraw;
	for(auto[a,b,t,c] : edges) {
		if(Union(a,b)) {
			wynik.first += t;
			wynik.second += c;
			kraw.push_back({a,b});
		}
	}
	if(wynik.first * wynik.second < best.first * best.second) {
		best = wynik;
		res = kraw;
	}
	return wynik;
}

void rek(ll t1, ll c1, ll t2, ll c2) {
	ll a = c2 - c1;
	ll b = t1 - t2;
	ll c = a*t1 + b*c1;
	auto[t3,c3] = mst(a,b);
	if(t3*a + c3*b == c) return;
	rek(t1,c1,t3,c3);
	rek(t3,c3,t2,c2);
}	

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for(ll i=0; i<m; ++i) {
		Edge e;
		cin >> e.a >> e.b >> e.t >> e.c;
		edges.push_back(e);
	}
	auto[t1,c1] = mst(0,1);
	auto[t2,c2] = mst(1,0);
	rek(t1, c1, t2, c2);
	cout << best.first << " " << best.second << "\n";
	for(auto[a,b] : res) cout << a << " " << b << "\n";

	return 0;
}

• Subtask 1: 100 / 100