// Source: https://oj.uz/problem/view/balkan11_timeismoney
//
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define FOR(i, a, b) for (ll i = (a); i<b; i++)
bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }
bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }
vector<array<ll, 4> > e;
ll n;
struct DSU {
vi p;
DSU(ll sz) : p(sz, -1) {}
ll get(ll cur) {
if (p[cur] < 0) return cur;
else return p[cur] = get(p[cur]);
}
bool unite(ll a, ll b) {
a = get(a);
b = get(b);
if (a == b) return false;
if (-p[a] > -p[b]) swap(a, b);
p[b] += p[a];
p[a] = b;
return true;
}
};
vpii best;
ll mn = 1e18;
pii pr;
pii solve(ll w1, ll w2) {
// cout << w1 << w2 << endl;
assert(w1 >= 0 && w2 >= 0);
sort(e.begin(), e.end(), [&](array<ll, 4> a, array<ll, 4> b) {
return w1 * a[2] + w2 * a[3] < w1 * b[2] + w2 * b[3];
});
DSU dsu(n);
vpii sol;
ll c = 0, t= 0;
for (auto val: e) {
if (dsu.unite(val[0], val[1])) {
sol.pb({val[0], val[1]});
t += val[2];
c += val[3];
}
}
if (t * c < mn) {
best = sol;
pr = {t, c};
}
assert(sol.size() == n-1);
return {t, c};
}
ll cross(pii a, pii b, pii c) {
// cout << a.f
return (b.f - a.f) * (c.s - a.s) - (b.s - a.s) * (c.f - a.f);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll m;
cin >> n >> m;
FOR(i, 0, m) {
ll a, b, c, d;
cin >> a >> b >> c >> d;
e.pb({a, b, c, d});
}
pii A = solve(1, 0);
pii B = solve(0, 1);
// cout << B.f << ' ' << B.s << endl;
// cout << A.f << ' ' << A.s << endl;
queue<pair<pii, pii> > q;
q.push({A, B});
// cout << cross({1, 0}, {0, 1}, {0, 0}) << endl;
while (!q.empty()) {
auto cur = q.front();
q.pop();
tie(A, B) = cur;
// cout << A.f << B
pii here = solve((B.f - A.f), (A.s - B.s));
// cout << here.f * here.s << endl;
if (cross(B, A, here) <= 0) continue;
q.push({A, here});
q.push({here, B});
}
cout << pr.f << ' ' << pr.s << endl;
for (auto val: best) cout << val.f << ' ' << val.s << endl;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from timeismoney.cpp:4:
timeismoney.cpp: In function 'pii solve(ll, ll)':
timeismoney.cpp:75:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
75 | assert(sol.size() == n-1);
| ~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Incorrect |
4 ms |
992 KB |
Output isn't correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 12 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 13 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 14 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 15 |
Incorrect |
1 ms |
416 KB |
Output isn't correct |
| 16 |
Incorrect |
3 ms |
348 KB |
Output isn't correct |
| 17 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 18 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 19 |
Incorrect |
6 ms |
992 KB |
Output isn't correct |
| 20 |
Incorrect |
6 ms |
992 KB |
Output isn't correct |
