# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
503696 | XII | timeismoney (balkan11_timeismoney) | C++17 | 103 ms | 588 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "timeismoney_TernarySearch"
void Fi(){
if(fopen(PROB".inp", "r")){
freopen(PROB".inp", "r", stdin);
freopen(PROB".out", "w", stdout);
}
}
const int N = 200 + 1;
const int M = 10000 + 1;
using ldb = long double;
const ldb MAX = 1e5;
struct edge{
int u, v, t, c;
ldb w;
const bool operator<(const edge &ot){
return w < ot.w;
}
};
vector<edge> ed;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
int n, m;
pl ans;
pi mst[N];
int cnt;
int par[N];
void init(){
FOR(i, 0, n) par[i] = -1;
}
int root(int v){
return (par[v] < 0) ? v : par[v] = root(par[v]);
}
bool join(int x, int y){
if((x = root(x)) == (y = root(y))) return false;
if(-par[x] < -par[y]) swap(x, y);
par[x] += par[y];
par[y] = x;
return true;
}
ll check(const double &X){
for(edge &x: ed){
x.w = (x.c * X + x.t * (MAX - X));
}
sort(ALL(ed));
cnt = 0;
ans = {0, 0};
init();
for(edge x: ed){
if(join(x.u, x.v)){
ans.fi += x.t;
ans.se += x.c;
mst[++cnt] = {x.u, x.v};
}
}
return ans.fi * ans.se;
}
int main(){
IOS;
Fi();
cin >> n >> m;
ed.resize(m);
for(edge &x: ed) cin >> x.u >> x.v >> x.t >> x.c;
ldb l = 0, r = MAX;
for(int step = 1; step <= 100; ++step){
ldb m1 = (2 * l + r) / 3;
ldb m2 = (l + r * 2) / 3;
if(check(m1) < check(m2)) r = m2;
else l = m1;
}
check(l);
cout << ans.fi << " " << ans.se << "\n";
FOR(i, 1, n) cout << mst[i].fi << " " << mst[i].se << "\n";
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |