Submission #619943

#	Time	Username	Problem	Language	Result	Execution time	Memory
619943		chuangsheep	timeismoney (balkan11_timeismoney)	C++11	95 / 100	475 ms	852 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<ll, ll>;
using Edge = array<ll, 5>;

struct DSU
{
  vector<ll> g;
  DSU(ll n) : g(n, -1) {}
  ll find(ll a)
  {
    if (g[a] < 0)
      return a;
    else
      return g[a] = find(g[a]);
  }
  bool unite(ll a, ll b)
  {
    a = find(a);
    b = find(b);
    if (a == b)
      return false;
    if (g[a] > g[b])
      swap(a, b);
    g[a] += g[b];
    g[b] = a;
    return true;
  }
};

pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
{
  sort(begin(edges), end(edges), [&](const Edge &e1, const Edge &e2)
       { return weights[e1[4]] < weights[e2[4]]; });
  DSU dsu(n);
  vector<ll> mst;
  ll t = 0;
  ll c = 0;
  for (Edge &e : edges)
  {
    if (dsu.unite(e[0], e[1]))
    {
      t += e[2];
      c += e[3];
      mst.push_back(e[4]);
    }
  }
  return {{t, c}, mst};
}

ll cross(pii A, pii B, pii C)
{
  pii AB = {B.first - A.first, B.second - A.second};
  pii AC = {C.first - A.first, C.second - A.second};
  return AB.first * AC.second - AB.second * AC.first;
}

int main()
{
#if defined(DEBUG) && !defined(ONLINE_JUDGE)
  // DEBUG
  cerr << "DEBUG flag set - see test.out for output\n";
  freopen("/home/chuang/shared-drives/G:/repos/cp/ois/boi11/timeismoney/test.in", "r", stdin);
  freopen("/home/chuang/shared-drives/G:/repos/cp/ois/boi11/timeismoney/test.out", "w", stdout);
#else
  cin.tie(0)->sync_with_stdio(false);
#endif

  ll N, M;
  cin >> N >> M;

  vector<Edge> edges(M);
  for (ll i = 0; i < M; i++)
  {
    ll x, y, t, c;
    cin >> x >> y >> t >> c;
    edges[i] = {x, y, t, c, i};
  }

  vector<ll> best_MST;
  pii best_V = {1e8, 1e8};

  vector<ll> weights(M);
  for (ll i = 0; i < M; i++)
  {
    weights[edges[i][4]] = edges[i][2];
  }
  pii A;
  tie(A, best_MST) = kruskal(N, edges, weights);
  best_V = A;
  for (ll i = 0; i < M; i++)
  {
    weights[edges[i][4]] = edges[i][3];
  }
  pii B = kruskal(N, edges, weights).first;

  stack<pair<pii, pii>> to_search;
  to_search.push({A, B});

  while (!to_search.empty())
  {
    tie(A, B) = to_search.top();
    to_search.pop();

    for (ll i = 0; i < M; i++)
    {
      weights[edges[i][4]] = edges[i][3] * (B.first - A.first) -
                             edges[i][2] * (B.second - A.second);
    }
    pii C;
    vector<ll> current_MST;
    tie(C, current_MST) = kruskal(N, edges, weights);

    if (cross(A, B, C) >= 0)
      continue;

    if ((ll)C.first * C.second < (ll)best_V.first * best_V.second)
    {
      best_V = C;
      best_MST = current_MST;
    }

    to_search.push({A, C});
    to_search.push({C, B});
  }

  cout << best_V.first << " " << best_V.second << "\n";
  sort(begin(edges), end(edges), [](const Edge &e1, const Edge &e2)
       { return e1[4] < e2[4]; });
  for (ll &id : best_MST)
  {
    cout << edges[id][0] << " " << edges[id][1] << "\n";
  }
}

• Subtask 1: 95 / 100