Submission #469283

#	Time	Username	Problem	Language	Result	Execution time	Memory
469283		Autron	timeismoney (balkan11_timeismoney)	C++14	100 / 100	110 ms	916 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct edge{
	int a, b, c, t;
	long double val;
	
	bool operator<(const edge& ot) const{
		return val<ot.val;
	}

};

int n, m;
vector<edge> v;
vector<int> fat, sz;
int solc, solt;
vector<edge> ans;

int get(int x){
	if(x==fat[x]) return x;
	return fat[x]=get(fat[x]);
}

void join(edge x){
	int a=get(x.a), b=get(x.b);
	if(a==b) return;
	solc+=x.c;
	solt+=x.t;
	ans.push_back(x);	
	if(sz[a]<sz[b]) swap(a, b);
	sz[a]+=sz[b];
	fat[b]=a;
}

int check(long double rat){
	for(int i=0;i<n;++i) fat[i]=i, sz[i]=1;
	for(int i=0;i<m;++i) v[i].val=v[i].c*rat+v[i].t*((long double)1e5-rat);
	sort(v.begin(), v.end());
	solc=0, solt=0;
	ans.clear();
	for(int i=0;i<m;++i){
		join(v[i]);
	}
	return solc*solt;
}

int32_t main(){
	cin>>n>>m;
	v.resize(m);
	for(int i=0;i<m;++i){
		cin>>v[i].a>>v[i].b>>v[i].t>>v[i].c;
	}
	fat.resize(n), sz.resize(n);
	long double st=0, dr=1e5;
	while((dr-st)>1e-7){
		long double m1=(2*st+dr)/3;
		long double m2=(st+2*dr)/3;
		if(check(m1)<check(m2)) dr=m2;
		else st=m1;
	}
	check(st);
	int sumc=0, sumt=0;
	for(auto it:ans){
		sumc+=it.c, sumt+=it.t;
	}
	cout<<sumt<<" "<<sumc<<"\n";
	for(auto it:ans) cout<<it.a<<" "<<it.b<<"\n";
}

• Subtask 1: 100 / 100