Submission #660807

#	Time	Username	Problem	Language	Result	Execution time	Memory
660807		600Mihnea	timeismoney (balkan11_timeismoney)	C++17	100 / 100	436 ms	604 KiB

timeismoney

bool home = 0;

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge
{
  int a;
  int b;
  int x;
  int y;
};

ll coef;
ll total;

bool operator < (Edge first, Edge second)
{
  return coef * first.x + (total - coef) * first.y < coef * second.x + (total - coef) * second.y;
}

int n;
int m;
vector<Edge> edges;
vector<int> t;
vector<int> P;
vector<int> S;

void clr()
{
  t.resize(n);
  iota(t.begin(), t.end(), 0);
}

int root(int a)
{
  if (t[a] == a)
  {
    return a;
  }
  else
  {
    return t[a] = root(t[a]);
  }
}

void join(int a, int b)
{
  t[root(a)] = root(b);
}

ll get(ll c)
{
  P.clear();
  coef = c;
  sort(edges.begin(), edges.end());
  clr();
  int X = 0, Y = 0;
  vector<pair<int, int>> T;
  for (auto &it : edges)
  {
    if (root(it.a) != root(it.b))
    {
      join(it.a, it.b);
      X += it.x;
      Y += it.y;
      T.push_back({it.a, it.b});
    }
  }
  P.push_back(X);
  P.push_back(Y);
  for (auto &IT : T)
  {
    P.push_back(IT.first);
    P.push_back(IT.second);
  }
  return 1LL * X * Y;
}

int main()
{
  if (home == 0)
  {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  }
  else
  {
    freopen ("input.txt", "r", stdin);
  }

  cin >> n >> m;
  edges.resize(m);
  for (auto &it : edges)
  {
    cin >> it.a >> it.b >> it.x >> it.y;
  }

  total = (ll) 1e9;

  ll sol = (ll) 1e18;

  for (ll c = 0; c <= total; c += (ll) 1e6)
  {
    ll cur = get(c);
    if (cur < sol)
    {
      sol = cur;
      S = P;
    }
  }

  ///cout << sol << "\n";
  for (int i = 0; i < (int) S.size(); i++)
  {
    cout << S[i] << " ";
    if (i % 2 == 1)
    {
      cout << "\n";
    }
  }

  return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:91:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen ("input.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100