Submission #986121

#TimeUsernameProblemLanguageResultExecution timeMemory
986121beabosstimeismoney (balkan11_timeismoney)C++14
5 / 100
2065 ms14116 KiB
// 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}; } return {t, c}; } ll cross(pii a, pii b, pii c) { 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}); 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...