oj.uz

Submission #726884

# Submission time Handle Problem Language Result Execution time Memory
726884 2023-04-19T13:40:19 Z josanneo22 timeismoney (balkan11_timeismoney) C++17
100 / 100
 42 ms 848 KB 
#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) > 2) {
		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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Correct 29 ms 848 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 8 ms 340 KB Output is correct
17 Correct 9 ms 340 KB Output is correct
18 Correct 8 ms 424 KB Output is correct
19 Correct 42 ms 848 KB Output is correct
20 Correct 42 ms 848 KB Output is correct