Submission #621370

#	Time	Username	Problem	Language	Result	Execution time	Memory
621370		chuangsheep	timeismoney (balkan11_timeismoney)	C++11	100 / 100	450 ms	692 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<int, int>;
// [town-x, town-y, time, cost, id]
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]);
  }
  /**
   * If a and b are already in the same set, return false and do nothing.
   * Otherwise, merge set a and b into one set and return true.
   */
  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;
  }
};

/**
 * Kruskal's Algorithm to find a MST with given edges and weights. Returns the
 * time and cost as pair<int,int> as well as ids of edges of the MST as
 * vector<int>.
 */
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};
}

/**
 * Calculate the signed area of the triangle ABP. This value is negativ if point
 * P is on the right side of vector AB.
 */
ll area(pii A, pii B, pii P) {
  pii AB = {B.first - A.first, B.second - A.second};
  pii AC = {P.first - A.first, P.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};
  }

  // The best Minimum Spanning Tree found so far.
  vector<int> best_MST;
  // The sum of time and cost w.r.t. best_MST.
  pii best_V = {1e8, 1e8};
  vector<int> current_MST;
  pii A, B, P;
  // The weights used by Kruskal's Algorithm to determine the MST.
  vector<int> weights(M);

  // A corresponds to the values of the MST if we only minimize the time
  for (int i = 0; i < M; i++) {
    weights[edges[i][4]] = edges[i][2];
  }
  tie(A, best_MST) = kruskal(N, edges, weights);
  best_V = A;

  // B corresponds to values of the MST if we only minimize the cost
  for (int i = 0; i < M; i++) {
    weights[edges[i][4]] = edges[i][3];
  }
  tie(B, current_MST) = kruskal(N, edges, weights);
  // If solution B is better than A, update the best solution
  if ((ll)B.first * B.second < (ll)A.first * A.second) {
    best_V = B;
    best_MST = current_MST;
  }

  // Search recursively for points on lower convex hull of the solution space
  stack<pair<pii, pii>> to_search;
  to_search.push({A, B});
  while (!to_search.empty()) {
    tie(A, B) = to_search.top();
    to_search.pop();

    /*
     * Since P is on the right side of vector AB, the signed area is negativ.
     * Thus, to maximize the unsigned area of triangle ABP, we should minimize
     * this signed value.
     */
    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);
    }
    tie(P, current_MST) = kruskal(N, edges, weights);

    /*
     * If P is on the left side of vector AB, we can terminate the search
     * on this branch. Note that the "left side of vector AB" is the right side
     * on the coordinate system.
     */
    if (area(A, B, P) >= 0) {
      continue;
    }

    // Compare the V value and update the best result if needed.
    if ((ll)P.first * P.second < (ll)best_V.first * best_V.second) {
      best_V = P;
      best_MST = current_MST;
    }

    /*
     * Search further with the new acquired point P to see if there is another
     * point that is on a hyperbola further left than P.
     */
    to_search.push({A, P});
    to_search.push({P, 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