Submission #619972

#	Time	Username	Problem	Language	Result	Execution time	Memory
619972		chuangsheep	timeismoney (balkan11_timeismoney)	C++11	100 / 100	439 ms	596 KiB

timeismoney

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

struct DSU
{
  vector<int> g;
  DSU(int n) : g(n, -1) {}
  int find(int a)
  {
    if (g[a] < 0)
      return a;
    else
      return g[a] = find(g[a]);
  }
  bool unite(int a, int 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<int>> kruskal(int n, vector<Edge> &edges, vector<int> &weights)
{
  sort(begin(edges), end(edges), [&](const Edge &e1, const Edge &e2)
       { return weights[e1[4]] < weights[e2[4]]; });
  DSU dsu(n);
  vector<int> mst;
  int t = 0;
  int 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 area(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()
{
  int N, M;
  cin >> N >> M;

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

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

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

  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 (int 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;
    tie(C, current_MST) = kruskal(N, edges, weights);

    if (area(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 (int &id : best_MST)
  {
    cout << edges[id][0] << " " << edges[id][1] << "\n";
  }
}

• Subtask 1: 100 / 100