Submission #1010342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010342		vjudge1	timeismoney (balkan11_timeismoney)	C++17	100 / 100	120 ms	860 KiB

timeismoney

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

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef long double ld;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

struct edge{
	int a, b, c, t;
	ld val;

};
 
int n, m, st, sc;
vector<edge> v, ans;
vi par, sz;

bool cmp(edge &a, edge &b){
	return a.val < b.val;
}

int find(int x){
	return par[x] == x ? x : par[x] = find(par[x]);
}

void unite(edge &x){
	int a = find(x.a), b = find(x.b);
	if(a == b) return;
	if(sz[a] < sz[b]) swap(a, b);
	sz[a] += sz[b];
	par[b] = a;
	sc += x.c;
	st += x.t;
	ans.PB(x);
}

int check(ld rat){
	for(int i=0; i<n; i++) par[i] = i, sz[i] = 1;
	for(int i=0; i<m; i++) v[i].val = v[i].c * rat + v[i].t * ((ld)1e6 - rat);
	sort(v.begin(), v.end(), cmp);
	sc = st = 0;
	ans.clear();
	for(int i=0; i<m; i++) unite(v[i]);
	return sc * st;
}
 
void solve(){
	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;
	par.resize(n);
	sz.resize(n);
	
	ld lo=0, hi=1e6;
	while(abs(lo - hi) > 1e-8){
		ld m1 = (2*lo + hi) / 3;
		ld m2 = (lo + 2*hi) / 3;
		if(check(m1) < check(m2)) hi = m2;
		else lo = m1;
	}
	check(lo);
	cout << st << " " << sc << "\n";
	for(auto &x : ans) cout << x.a << " " << x.b << "\n";
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
	return 0;
}

• Subtask 1: 100 / 100