Submission #480776

#	Time	Username	Problem	Language	Result	Execution time	Memory
480776		daongocha	timeismoney (balkan11_timeismoney)	C++14	60 / 100	1154 ms	976 KiB

timeismoney

#include <bits/stdc++.h>

#define int long long

#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);
 
using namespace std;

const int MAXN = 205;

struct edge {
	int u, v, t, c;
};

#define ld long double
const ld EPS = 1e-9;
ld q;

ld num(edge a) {
	return a.t * q + a.c * (1e6 - q);
}

bool cmp(edge a, edge b) {
	return num(a) + EPS < num(b);
}

vector<edge> edges;
int n, m;

int dsu[MAXN];

int Find(int u) {
	if (u == dsu[u]) return u;
	return dsu[u] = Find(dsu[u]);
}

void Union(int u, int v) {
	u = Find(u), v = Find(v);
	if (u != v) dsu[v] = u;
}

int solve(ld okayge) {
	q = okayge;
	sort(edges.begin(), edges.end(), cmp);
	for (int i = 1; i <= n; i++) dsu[i] = i;
	int tott = 0, totc = 0;
	for (auto e: edges) {
		int u = e.u, v = e.v;
		if (Find(u) != Find(v)) {
			Union(u, v);
			tott += e.t;
			totc += e.c;
		}
	}
	return tott * totc;
}

void print(ld okayge) {
	q = okayge;
	sort(edges.begin(), edges.end(), cmp);
	for (int i = 1; i <= n; i++) dsu[i] = i;
	int tott = 0, totc = 0;
	for (auto e: edges) {
		int u = e.u, v = e.v;
		if (Find(u) != Find(v)) {
			Union(u, v);
			tott += e.t;
			totc += e.c;
		}
	}
	cout << tott << ' ' << totc << '\n';
	for (int i = 1; i <= n; i++) dsu[i] = i;
	for (auto e: edges) {
		int u = e.u, v = e.v;
		if (Find(u) != Find(v)) {
			Union(u, v);
			cout << u - 1 << ' ' << v - 1 << '\n';
		}
	}
}

signed main() {
	#ifndef PICHU_LOCAL_DEF
		//fileopen1("LAH");
	#endif

	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> m;

	q = 0.1;

	for (int i = 1, u, v, t, c; i <= m; i++) {
		cin >> u >> v >> t >> c;
		u++; v++;
		edges.push_back({u, v, t, c});
	}

	ld l = 0, r = 1e6;
	for (int i = 1; i <= 400; i++) {
		ld lm = l + (r - l) / 3, rm = r - (r - l) / 3;
		if (solve(lm) > solve(rm)) l = rm;
		else r = lm;
	}

	print(l);
}	

• Subtask 1: 60 / 100