Submission #207598

#	Time	Username	Problem	Language	Result	Execution time	Memory
207598		junodeveloper	timeismoney (balkan11_timeismoney)	C++17	100 / 100	105 ms	1140 KiB

timeismoney

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
struct edge {
	int u,v;
	int v1,v2;
	ld val;
	bool operator<(const edge& b)const {
		return val<b.val;
	}
};
const ld R=1e5;
int n,m;
int par[210];
vector<edge> e;
int pn(int u){return u==par[u]?u:(par[u]=pn(par[u]));}
void us(int a,int b) {
	a=pn(a),b=pn(b);
	par[b]=a;
}
pair<ll,vector<edge>> f(ld x) {
	for(int i=0;i<=n;i++)par[i]=i;
	for(auto& it:e)it.val=it.v1*x+it.v2*(R-x);
	sort(e.begin(),e.end());
	ll s1=0,s2=0;
	vector<edge> r;
	for(auto& it:e) {
		if(pn(it.u)!=pn(it.v)) {
			us(it.u,it.v);
			s1+=it.v1;
			s2+=it.v2;
			r.pb(it);
		}
	}
	return {s1*s2,r};
}
int main() {
	ios::sync_with_stdio(stdin);cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++) {
		int x,y,v1,v2;
		cin>>x>>y>>v1>>v2;
		e.pb({x,y,v1,v2});
	}
	ld lo=0,hi=R;
	while(abs(lo-hi)>1e-7) {
		ld m1=(lo*2+hi)/3;
		ld m2=(lo+hi*2)/3;
		if(f(m1).fi<f(m2).fi) hi=m2;
		else lo=m1;
	}
	vector<edge> r=f(lo).se;
	ll s1=0,s2=0;
	for(auto& it:r) {
		s1+=it.v1;
		s2+=it.v2;
	}
	cout<<s1<<' '<<s2<<'\n';
	for(auto& it:r)cout<<it.u<<' '<<it.v<<'\n';
	return 0;
}

• Subtask 1: 100 / 100