Submission #1141714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141714		otesunki	timeismoney (balkan11_timeismoney)	C++20	60 / 100	8 ms	704 KiB

timeismoney

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

int N, M;
std::vector<std::tuple<int, int>> chosen;
std::vector<std::tuple<int, int, int, int>> edges;
std::vector<int> reduction;

int main(void) {
  std::cin >> N >> M;
  reduction.resize(N);
  for (int i = 0; i < N; ++i) {
    reduction[i] = i;
  }
  for (int i = 0; i < M; ++i) {
    int a, b, t, c;

    std::cin >> a >> b >> t >> c;
    edges.push_back({a, b, t, c});
  }
  int time = 0, cost = 0;
  for (;;) {
    int mintime = -1, mincost = -1, mina = -1, minb = -1;
/*
    std::cout << "    time=" << time << "\n";
    std::cout << "    cost=" << cost << "\n";
    for (int i = 0; i < edges.size(); ++i) {
      std::cout << std::get<0>(edges[i]) << " [" << reduction[std::get<0>(edges[i])] << "] -> "
                << std::get<1>(edges[i]) << " [" << reduction[std::get<1>(edges[i])] << "] (t="
                << std::get<2>(edges[i]) << " | c=" << std::get<3>(edges[i]) << ")\n";
    }
*/
    for (int i = 0; i < edges.size(); ++i) {
      int thistime = (std::get<2>(edges[i]) + time);
      int thiscost = (std::get<3>(edges[i]) + cost);
/*
      std::cout << "thistime=" << thistime << "\n";
      std::cout << "thiscost=" << thiscost << "\n";
      std::cout << "mintime=" << mintime << "\n";
      std::cout << "mincost=" << mincost << "\n";
*/
      if ((thistime * thiscost < mintime * mincost) || (mina == -1)) {
        mintime = thistime;
        mincost = thiscost;
        mina = std::get<0>(edges[i]);
        minb = std::get<1>(edges[i]);
      }
    }
    time = mintime;
    cost = mincost;
    int minredi = 201, maxredi = 0;
    chosen.push_back({mina, minb});
    int reductionminb = reduction[minb];
    int reductionmina = reduction[mina];
/*
    std::cout << "merge " << reductionmina << " with " << reductionminb << "\n";
*/
    for (int i = 0; i < N; ++i) {
      if (reduction[i] == reductionminb) {
        reduction[i] = reductionmina;
      }
      if (reduction[i] < minredi) {
        minredi = reduction[i];
      }
      if (reduction[i] > maxredi) {
        maxredi = reduction[i];
      }
    }
    if (minredi == maxredi) {
      break;
    }
    auto it = std::remove_if(std::begin(edges), std::end(edges), [](auto edge) {
/*
      std::cout << "  compare " << reduction[std::get<0>(edge)] << " & " << reduction[std::get<1>(edge)] << "\n";
*/
      return reduction[std::get<0>(edge)] == reduction[std::get<1>(edge)];
    });
    edges.erase(it, std::end(edges));
  }

  std::cout << time << " " << cost << "\n";
  for (auto edge : chosen) {
    std::cout << std::get<0>(edge) << " " << std::get<1>(edge) << "\n";
  }
  return 0;
}

• Subtask 1: 60 / 100