#include <bits/stdc++.h>
using namespace std;
struct edge{
int a, b, t, c;
edge(){}
};
struct halfplane{
long long A, B, C;
halfplane(){}
halfplane(long long A, long long B, long long C): A(A), B(B), C(C){}
};
struct result{
long long t, c, a, b;
result(long long t, long long c, long long a, long long b): t(t), c(c), a(a), b(b){}
bool operator <(const result& r) const{
return t * c < r.t * r.c;
}
};
int findr(vector <int>& d, int u){
if(d[u] == u)return u;
else return d[u] = findr(d, d[u]);
}
vector < pair <int, int> > res;
long long mst(int n, vector <edge>& e, long long a, long long b, bool construct = false){
vector <int> d(n);
for(int i = 0; i < n; i++)
d[i] = i;
sort(e.begin(), e.end(), [&](const edge& x, const edge& y){
return x.t * a + x.c * b < y.t * a + y.c * b;
});
long long cost = 0;
for(auto[u, v, t, c] : e){
int ur = findr(d, u), vr = findr(d, v);
if(ur == vr)continue;
if(construct)res.emplace_back(u, v);
cost += t * a + c * b;
d[ur] = vr;
}
return cost;
}
bool check(const halfplane& L, const halfplane& R, const halfplane& mid){
return (L.A * R.B - L.B * R.A) * mid.C + (L.B * R.C - L.C * R.B) * mid.A + (L.C * R.A - L.A * R.C) * mid.B == 0;
}
result calc(int n, vector <edge>& e, const halfplane& L, const halfplane& R){
//cout << L.A << ',' << L.B << ',' << L.C << ' ' << R.A << ',' << R.B << ',' << R.C << endl;
halfplane mid = halfplane(L.A + R.A, L.B + R.B, mst(n, e, L.A + R.A, L.B + R.B));
if(!check(L, R, mid)){
result ret1 = calc(n, e, L, mid);
result ret2 = calc(n, e, mid, R);
if(ret1 < ret2)return ret1;
else return ret2;
}else{
return result((L.C * R.B - R.C * L.B) / (L.A * R.B - R.A * L.B), (L.C * R.A - R.C * L.A) / (L.B * R.A - R.B * L.A),
L.A + R.A, L.B + R.B);
}
}
int main(){
//cout << check(halfplane(1, 1, 18), halfplane(0, 1, 11), halfplane(1, 2, 29)) << endl;
int n, m;
scanf("%d %d", &n, &m);
vector <edge> e(m);
for(int i = 0; i < m; i++)
scanf("%d %d %d %d", &e[i].a, &e[i].b, &e[i].t, &e[i].c);
result ret = calc(n, e, halfplane(1, 0, mst(n, e, 1, 0)), halfplane(0, 1, mst(n, e, 0, 1)));
printf("%lld %lld\n", ret.t, ret.c);
mst(n, e, ret.a, ret.b, true);
for(auto[u, v] : res)
printf("%d %d\n", u, v);
return 0;
}
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
70 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
timeismoney.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | scanf("%d %d %d %d", &e[i].a, &e[i].b, &e[i].t, &e[i].c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
512 KB |
Output is correct |
| 8 |
Correct |
7 ms |
640 KB |
Output is correct |
| 9 |
Correct |
1 ms |
256 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
256 KB |
Output is correct |
| 12 |
Correct |
3 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
38 ms |
384 KB |
Output is correct |
| 15 |
Correct |
28 ms |
384 KB |
Output is correct |
| 16 |
Correct |
296 ms |
504 KB |
Output is correct |
| 17 |
Correct |
327 ms |
384 KB |
Output is correct |
| 18 |
Correct |
291 ms |
504 KB |
Output is correct |
| 19 |
Correct |
1396 ms |
812 KB |
Output is correct |
| 20 |
Correct |
1515 ms |
760 KB |
Output is correct |
