Submission #1287594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287594		LIA	timeismoney (balkan11_timeismoney)	C++17	100 / 100	944 ms	2432 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>

struct Dsu {
  vll p, sz;

  Dsu(ll n) : p(n), sz(n, 1) {
    iota(p.begin(), p.end(), 0);
  }

  ll find(ll v) {
    if (p[v] == v)
      return v;
    return p[v] = find(p[v]);
  }

  bool uni(ll a, ll b) {
    ll x = find(a), y = find(b);
    if (x == y)
      return 0;
    if (sz[x] < sz[y])
      swap(x, y);
    sz[x] += sz[y];
    p[y] = x;
    return 1;
  }
};

struct Res {
  ll T, C;
  vector<pair<ll, ll>> e;
};

int main() {
  ll n, m;
  cin >> n >> m;
  vector<tuple<ll, ll, ll, ll>> vec;
  for (ll i = 0; i < m; ++i) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    vec.push_back({c, d, a, b});
  }

  auto run = [&](ll p, ll q) -> Res {
    vector<ll> id(m);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](ll i, ll j) {
      auto [ti, ci, ai, bi] = vec[i];
      auto [tj, cj, aj, bj] = vec[j];
      ll wi = ti * q + ci * p;
      ll wj = tj * q + cj * p;
      if (wi != wj)
        return wi < wj;
      if (ti != tj)
        return ti < tj;
      if (ci != cj)
        return ci < cj;
      if (ai != aj)
        return ai < aj;
      return bi < bj;
    });
    Dsu dsu(n);
    ll T = 0, C = 0, used = 0;
    vector<pair<ll, ll>> e;
    for (ll k = 0; k < id.size() && used < n - 1; ++k) {
      auto [t, c, a, b] = vec[id[k]];
      if (dsu.uni(a, b)) {
        ++used;
        T += t;
        C += c;
        e.push_back({a, b});
      }
    }
    return {T, C, e};
  };

  Res A = run(0, 1);
  Res B = run(1, 0);

  vector<Res> ans;
  ans.push_back(A);
  ans.push_back(B);

  function<void(const Res&, const Res&)> hull = [&](const Res& X, const Res& Y) {
    if (X.T == Y.T && X.C == Y.C)
      return;
    if (X.C == Y.C)
      return;
    ll p = (Y.T - X.T);
    ll q = (X.C - Y.C);
    Res Z = run(p, q);
    if ((Z.T == X.T && Z.C == X.C) || (Z.T == Y.T && Z.C == Y.C))
      return;
    __int128 dx = ((__int128)Y.T - X.T);
    __int128 dy = ((__int128)Y.C - X.C);
    __int128 zx = ((__int128)Z.T - X.T);
    __int128 zy = ((__int128)Z.C - X.C);
    __int128 D = dx * zy - dy * zx;
    if (D < 0) {
      ans.push_back(Z);
      hull(X, Z);
      hull(Z, Y);
    }
  };

  hull(A, B);

  ll v = 4e18, cc = 0, tt = 0;
  vector<pair<ll, ll>> pairs2;
  for (auto& r : ans) {
    if (r.e.size() == n - 1) {
      ll val = r.T * r.C;
      if (val < v) {
        v = val;
        cc = r.C;
        tt = r.T;
        pairs2 = r.e;
      }
    }
  }

  cout << tt << " " << cc << "\n";
  for (auto [a, b] : pairs2)
    cout << a << " " << b << "\n";
}

• Subtask 1: 100 / 100