답안 #302617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
302617 2020-09-18T22:23:24 Z Mohammad_Yasser 시간이 돈 (balkan11_timeismoney) C++14
100 / 100
153 ms 1272 KB
#ifndef Local
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse4,sse4.2,popcnt,abm,mmx,avx")
#endif
#include <bits/stdc++.h>

using namespace std;

#define popCnt(x) (__builtin_popcountll(x))
#define sz(x) ((int)(x.size()))
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
typedef long long Long;
typedef double Double;

template <class U, class V>
istream& operator>>(istream& is, pair<U, V>& p) {
  is >> p.first >> p.second;
  return is;
}
template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (auto& x : v) {
    is >> x;
  }
  return is;
}

template <class T>
ostream& operator<<(ostream& os, vector<T>& v) {
  for (auto& x : v) {
    os << x << " ";
  }
  return os;
}

const Double EPS = 1e-10;

enum Relation { LESS_THAN, EQUAL, GREATER_THAN };

bool areEqual(Double x, Double y, Double eps = EPS) {
  auto diff = abs(x - y);
  x = abs(x), y = abs(y);
  if (diff <= eps) return true;
  if (min(x, y) <= eps) return false;
  return diff <= eps * max(x, y);
}

bool isZero(Double x, Double eps = EPS) { return abs(x) <= eps; }
bool isZero(Long x) { return x == 0; }

int compareDoubles(Double x, Double y, Double eps = EPS) {
  if (areEqual(x, y, eps)) return Relation::EQUAL;
  if (x < y) return Relation::LESS_THAN;
  return Relation::GREATER_THAN;
}

template <typename T = Double>
struct Point {
  typedef Point P;
  const static P Invalid;
  const static P Origin;

  T x = 0, y = 0;
  Point(T x, T y) : x(x), y(y) {}
  Point() {}
  pair<T, T> to_pair() const { return make_pair(x, y); }
  Point operator+(const Point& p) const { return Point{x + p.x, y + p.y}; }
  Point operator-(const Point& p) const { return Point{x - p.x, y - p.y}; }
  Point operator*(T c) const { return Point(x * c, y * c); }
  Point operator/(T c) const { return Point(x / c, y / c); }
  bool operator<(const Point& p) const {
    return (*this) != p && to_pair() < p.to_pair();
  }
  bool operator>(const Point& p) const { return (*this) != p && !(*this < p); }
  bool operator==(const Point& p) const {
    return isZero(this->x - p.x) && isZero(this->y - p.y);
  }
  bool operator!=(const Point& p) const { return !(*this == p); }
  T cross(const P& p) const { return x * p.y - y * p.x; }
  T cross(const P& a, const P& b) const { return (a - *this).cross(b - *this); }
  T dot(const P& p) const { return x * p.x + y * p.y; }
  P midPoint(const P& p) const { return ((*this) + p) / 2; }
  P getVector(const P& p) const { return p - (*this); }
  T dist2(const P& p) const { return getVector(p).dist2(); }
  T dist2() const { return (*this).dot(*this); }
  Double dist(const P& p) const { return sqrt(dist2(p)); }
  Double dist() const { return sqrt(dist2()); }
  P rotateCCW90() const { return P(-y, x); }
  friend istream& operator>>(istream& is, P& p) { return is >> p.x >> p.y; }

  friend ostream& operator<<(ostream& os, const P& p) {
    return os << p.x << " " << p.y;
  }
};

template <typename T>
const Point<T> Point<T>::Invalid = Point<T>(numeric_limits<T>::max(),
                                            numeric_limits<T>::max());
template <typename T>
const Point<T> Point<T>::Origin = Point<T>(0, 0);

typedef Point<Double> P;

bool areCollinear(const P& a, const P& b, const P& c) {
  return isZero(a.getVector(b).cross(c.getVector(b)));
}

const int N = 200;

struct Solution {
  Long t = 0, c = 0;
  vector<pair<int, int>> edges;
  P getP() const { return P(t, c); }
  Long score() const { return t * c; }
  bool operator<(const Solution& other) const {
    return score() < other.score();
  }
  bool operator==(const Solution& other) const {
    return t == other.t && c == other.c;
  }
};

int n;
vector<tuple<int, Long, Long>> adj[N];

Solution mst(Long coeff_x, Long coeff_y) {
  static const Long OO = LLONG_MAX / 2;
  static const Long VIS = OO - 1;
  static vector<Long> dist(N), best_t(N), best_c(N), best_parent(N);

  fill(all(dist), OO);
  dist[0] = 0;
  Solution sol;
  for (int i = 0; i < n; ++i) {
    int mn = min_element(all(dist)) - begin(dist);
    for (auto [v, t, c] : adj[mn]) {
      if (dist[v] == VIS) continue;
      Long tmp = t * coeff_x + c * coeff_y;
      if (tmp < dist[v]) {
        dist[v] = tmp;
        best_t[v] = t;
        best_c[v] = c;
        best_parent[v] = mn;
      }
    }
    dist[mn] = VIS;
    if (i != 0) {
      sol.t += best_t[mn];
      sol.c += best_c[mn];
      sol.edges.emplace_back(mn, best_parent[mn]);
    }
  }
  return sol;
}
Solution best;
void solve(const P& left_v, const P& right_v, const Solution& left_sol,
           const Solution& right_sol) {
  P mid = (left_sol.getP() - right_sol.getP())
              .rotateCCW90();  // Vector perpendicular to the segment connecting
                               // the left and right points.

  auto sol = mst(mid.x, mid.y);
  best = min(best, sol);
  if (areCollinear(left_sol.getP(), sol.getP(), right_sol.getP())) return;
  solve(left_v, mid, left_sol, sol);
  solve(mid, right_v, sol, right_sol);
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef Local
  freopen("test.in", "r", stdin);
#else
#define endl '\n'
#endif

  int m;
  cin >> n >> m;

  while (m--) {
    int u, v, t, c;
    cin >> u >> v >> t >> c;
    adj[u].emplace_back(v, t, c);
    adj[v].emplace_back(u, t, c);
  }

  P left_v(0, 1);
  P right_v(1, 0);
  auto left_sol = mst(left_v.x, left_v.y);
  auto right_sol = mst(right_v.x, right_v.y);
  best = min(left_sol, right_sol);
  if (!(left_sol == right_sol)) solve(left_v, right_v, left_sol, right_sol);
  cout << best.t << " " << best.c << endl;
  for (auto [u, v] : best.edges) {
    cout << u << " " << v << endl;
  }

  return 0;
}

Compilation message

timeismoney.cpp: In function 'Solution mst(Long, Long)':
timeismoney.cpp:137:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  137 |     for (auto [v, t, c] : adj[mn]) {
      |               ^
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:195:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  195 |   for (auto [u, v] : best.edges) {
      |             ^
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 5 ms 1152 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct
15 Correct 10 ms 384 KB Output is correct
16 Correct 48 ms 512 KB Output is correct
17 Correct 51 ms 512 KB Output is correct
18 Correct 49 ms 544 KB Output is correct
19 Correct 148 ms 1152 KB Output is correct
20 Correct 153 ms 1272 KB Output is correct