/// 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 bool 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;
}
Compilation message
timeismoney.cpp: In function 'void Fi()':
timeismoney.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | freopen(PROB".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | freopen(PROB".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
316 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
328 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
4 ms |
588 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
3 ms |
332 KB |
Output is correct |
| 15 |
Correct |
2 ms |
332 KB |
Output is correct |
| 16 |
Correct |
36 ms |
332 KB |
Output is correct |
| 17 |
Correct |
38 ms |
328 KB |
Output is correct |
| 18 |
Correct |
36 ms |
332 KB |
Output is correct |
| 19 |
Correct |
309 ms |
588 KB |
Output is correct |
| 20 |
Correct |
317 ms |
588 KB |
Output is correct |
