| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 503636 | XII | timeismoney (balkan11_timeismoney) | C++17 | 0 ms | 0 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.
/// https://oj.uz/problem/view/balkan11_timeismoney
#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 "balkan11_timeismoney"
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;
int n, m;
struct edge{
int u, v, t, c;
ll w;
const operator<(const edge &ot){
return w < ot.w;
}
};
vector<edge> ed;
using pi = pair<int, int>;
using point = pair<ll, ll>;
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;
}
/// at + bc = X -> slope = -b/a
point ans = {1e9, 1e9};
int cnt;
pi mst[N], tmp[N];
void checkPoint(const point &a){
if(a.fi * a.se > ans.fi * ans.se) return;
ans = a;
FOR(i, 0, n - 1) mst[i] = tmp[i];
}
point Go(ll a, ll b){
point res = {0, 0};
for(edge &x: ed){
x.w = (a * x.t + b * x.c);
}
cnt = 0;
init();
sort(ALL(ed));
for(edge x: ed){
if(join(x.u, x.v)){
res.fi += x.t;
res.se += x.c;
tmp[cnt++] = {x.u, x.v};
}
}
checkPoint(res);
return res;
}
ll CCW(const point &a, const point &b, const point &c){
return (b.fi - a.fi) * (c.se - a.se) - (c.fi - a.fi) * (b.se - a.se);
}
void Find(point l, point r){
point mid = Go(l.se - r.se, r.fi - l.fi);
if(CCW(l, mid, r) == 0) return;
checkPoint(mid);
Find(l, mid);
Find(mid, r);
}
int main(){
IOS;
Fi();
cin >> n >> m;
ed.resize(m);
for(edge &x: ed){
cin >> x.u >> x.v >> x.t >> x.c;
}
point p1 = Go(1, 0); checkPoint(p1);
point p2 = Go(0, 1); checkPoint(p2);
// cout << p1.fi << " " << p1.se << "\n";
// cout << p2.fi << " " << p2.se << "\n";
Find(p1, p2);
cout << ans.fi << " " << ans.se << "\n";
FOR(i, 0, n - 1) cout << mst[i].fi << " " << mst[i].se << "\n";
return 0;
}