Submission #1142258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142258		otesunki	timeismoney (balkan11_timeismoney)	C++20	5 / 100	6 ms	580 KiB

timeismoney

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <functional>

struct edge {
  unsigned int a, b, t, c;
};

struct edge untitled_algorithm(
  unsigned int N,
  std::vector<edge> *const out,
  std::vector<edge> *const graph,
  const unsigned int t_weight,
  const unsigned int c_weight
) {
  out->clear();
  out->reserve(N);

  auto costof = [=] (edge e) {
    return e.t * t_weight + e.c * c_weight;
  };

  std::sort(graph->begin(), graph->end(), [&] (edge a, edge b) {
    return costof(a) < costof(b);
  });

  struct cant_be_anonymous { unsigned int up, rank; };
  std::vector<cant_be_anonymous> dsu;
  dsu.reserve(N);
  for (unsigned int i = 0; i < N; ++i)
    dsu.push_back({i, 0});

  std::function<unsigned int(unsigned int)> repr;
  repr = [&] (unsigned int i) {
    if (dsu[i].up == i)
      return i;
    return dsu[i].up = repr(dsu[i].up);
  };

  auto merge = [&] (unsigned int i, unsigned int j) {
    unsigned int k = dsu[i].rank < dsu[j].rank ? i : j;

    dsu[k].up = i^j^k;
  };

  edge overall_motion = { 0, 0, 0, 0 };

  for (const edge e : *graph) {
    unsigned int a, b;
    a = repr(e.a);
    b = repr(e.b);
    if (a != b) {
      merge(a, b);
      out->push_back({e.a, e.b, e.t, e.c});
      overall_motion.t += e.t;
      overall_motion.c += e.c;
    }
  }

  return overall_motion;
}

int main(void) {
  unsigned int N, M;
  std::vector<edge> edges;

  std::cin >> N >> M;
  edges.reserve(M);
  for (unsigned int i = 0; i < M; ++i) {
    unsigned int a, b, t, c;

    std::cin >> a >> b >> t >> c;
    edges.push_back({a, b, t, c});
  }

  std::vector<edge> out;
  edge overall_t = untitled_algorithm(N, &out, &edges, 1, 0);
  edge overall_c = untitled_algorithm(N, &out, &edges, 0, 1);
  int tw = overall_t.t - overall_c.t;
  int cw = overall_c.c - overall_t.c;
  edge overall = untitled_algorithm(N, &out, &edges, tw, cw);

  std::cout << overall.t << " " << overall.c << "\n";
  for (edge e : out) {
    std::cout << e.a << " " << e.b << "\n";
  }
}

• Subtask 1: 5 / 100