oj.uz

Submission #726893

# Submission time Handle Problem Language Result Execution time Memory
726893 2023-04-19T13:49:16 Z josanneo22 timeismoney (balkan11_timeismoney) C++17
100 / 100
 38 ms 856 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;
	}
};
vector<int> par,sz;
int total_groups;
void init(int n){
	par.resize(n); sz.resize(n);
	for(int i=0;i<=n;i++){
		par[i]=i;
	}
}
int find(int x){
	if(par[x]==x) return x;
	else return par[x]=find(par[x]);
}
void unite(int x, int y) {
    x = find(x);  y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    par[y] = x;
}
bool same(int x,int y){
    x = find(x);
    y = find(y);
    if(x==y) return true;
    else return false;
}
//remember to init(n+5) and total_groups=n

const ld R = 1e5;
int n, m;
vector<edge> e;
pair<ll, vector<edge>> f(ld x) {
	init(n+1);
	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 (!same(it.u,it.v)) {
			unite(it.u, it.v);
			s1 += it.v1;
			s2 += it.v2;
			r.pb(it);
		}
	}
	return { s1 * s2,r };
}
int main() {
	ios::sync_with_stdio(0); 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 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 24 ms 856 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 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 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 7 ms 340 KB Output is correct
17 Correct 7 ms 340 KB Output is correct
18 Correct 7 ms 340 KB Output is correct
19 Correct 38 ms 856 KB Output is correct
20 Correct 38 ms 856 KB Output is correct