Submission #1268650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268650		nguyenphong233	timeismoney (balkan11_timeismoney)	C++17	100 / 100	53 ms	840 KiB

timeismoney

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define int long long
#define double long double 
#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)1e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n,m;
struct node{
	int x,y,t,c;
	double v;
}edge[MAX];
int par[MAX];
int find(int u){
	return (u == par[u] ? u : par[u] = find(par[u]));
}
int calc(double ratio,int cw = 0){
	for(int i = 1;i <= m;i++){
		edge[i].v = edge[i].t * ratio + edge[i].c * (1e15 - ratio); 
	}
	sort(edge + 1,edge + 1 + m,[&](const node &a,const node &b){
		return a.v < b.v;
	});
	for(int i = 1;i <= n;i++)par[i] = i;
	int t_ = 0,c_ = 0;
	vector<int> q;
	for(int i = 1;i <= m;i++){
		int u_ = find(edge[i].x);
		int v_ = find(edge[i].y);
		if(u_ == v_)continue;
		par[u_] = v_;
		t_ += edge[i].t;
		c_ += edge[i].c;
		q.push_back(i);
	}
	if(!cw)return t_ * c_;
	
	cout << t_ << " " << c_ << "\n";
	for(auto v : q)cout << edge[v].x - 1 << " " << edge[v].y - 1<< "\n";
	return 0;
}
signed main(){
	
	read();
	cin >> n >> m;
	for(int i = 1,x,y,u,v;i <= m;i++){
		cin >> x >> y >> u >> v;
		x++,y++;
		edge[i] = {x,y,u,v,0};
	}	
	
	double l = 0,r = 1e15;
	while(abs(l - r) > 1e-1){
		double m1 = l + (r - l) / 3;
		double m2 = r - (r - l) / 3;
		//cout << setprecision(8) << fixed << l << " " << r << " " << m1 << " " << m2 << '\n';
		if(calc(m1) < calc(m2))r = m2;
		else l = m1;
	}
	calc(l,1);
}

• Subtask 1: 100 / 100