oj.uz

답안 #621370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
621370 2022-08-03T18:06:50 Z chuangsheep 시간이 돈 (balkan11_timeismoney) C++11
100 / 100
 450 ms 692 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 12 ms 692 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 4 ms 212 KB Output is correct
15 Correct 3 ms 300 KB Output is correct
16 Correct 46 ms 356 KB Output is correct
17 Correct 49 ms 360 KB Output is correct
18 Correct 56 ms 340 KB Output is correct
19 Correct 419 ms 668 KB Output is correct
20 Correct 450 ms 668 KB Output is correct