Submission #619854

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
619854	2022-08-02T16:34:20 Z	chuangsheep	timeismoney (balkan11_timeismoney)	C++11	Compilation error	0 ms	0 KB

timeismoney

#include <bits/stdc++.h>
using namespace std;
using ll = long long ll;
using pii = pair<ll, ll>;
using Edge = array<ll, 5>;

struct DSU
{
  vector<ll> g;
  DSU(ll n) : g(n, -1) {}
  ll find(ll a)
  {
    if (g[a] < 0)
      return a;
    else
      return g[a] = find(g[a]);
  }
  bool unite(ll a, ll 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;
  }
};

pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
{
  sort(begin(edges), end(edges), [&](const Edge &e1, const Edge &e2)
       { return weights[e1[4]] < weights[e2[4]]; });
  DSU dsu(n);
  vector<ll> mst;
  ll t = 0;
  ll c = 0;
  for (Edge &e : edges)
  {
    if (dsu.unite(e[0], e[1]))
    {
      n--;
      t += e[2];
      c += e[3];
      mst.push_back(e[4]);
    }
  }
  return {{t, c}, mst};
}

ll cross(pii A, pii B, pii C)
{
  pii AB = {B.first - A.first, B.second - A.second};
  pii AC = {C.first - A.first, C.second - A.second};
  return AB.first * AC.second - AB.second * AC.first;
}

ll main()
{
#if defined(DEBUG) && !defined(ONLINE_JUDGE)
  // DEBUG
  cerr << "DEBUG flag set - see test.out for output\n";
  freopen("/home/chuang/shared-drives/G:/repos/cp/ois/boi11/timeismoney/test.in", "r", stdin);
  freopen("/home/chuang/shared-drives/G:/repos/cp/ois/boi11/timeismoney/test.out", "w", stdout);
#else
  cin.tie(0)->sync_with_stdio(false);
#endif

  ll N, M;
  cin >> N >> M;

  vector<Edge> edges(M);
  for (ll i = 0; i < M; i++)
  {
    ll x, y, t, c;
    cin >> x >> y >> t >> c;
    edges[i] = {x, y, t, c, i};
  }

  vector<ll> weights(M);

  for (ll i = 0; i < M; i++)
  {
    weights[edges[i][4]] = edges[i][2];
  }
  pii A = kruskal(N, edges, weights).first;
  for (ll i = 0; i < M; i++)
  {
    weights[edges[i][4]] = edges[i][3];
  }
  pii B = kruskal(N, edges, weights).first;

  stack<pair<pii, pii>> to_search;
  to_search.push({A, B});

  vector<ll> best_MST;
  pii best_V = {1e8, 1e8};
  while (!to_search.empty())
  {
    tie(A, B) = to_search.top();
    to_search.pop();

    for (ll i = 0; i < M; i++)
    {
      weights[edges[i][4]] = edges[i][3] * (B.first - A.first) -
                             edges[i][2] * (B.second - A.second);
    }
    pii C;
    vector<ll> current_MST;
    tie(C, current_MST) = kruskal(N, edges, weights);

    if (cross(A, B, C) >= 0)
      continue;

    if ((ll)C.first * C.second < (ll)best_V.first * best_V.second)
    {
      best_V = C;
      best_MST = current_MST;
    }

    to_search.push({A, C});
    to_search.push({C, 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 (ll &id : best_MST)
  {
    cout << edges[id][0] << " " << edges[id][1] << "\n";
  }
}

Compilation message

timeismoney.cpp:3:21: error: expected ';' before 'll'
    3 | using ll = long long ll;
      |                     ^~~
      |                     ;
timeismoney.cpp:4:18: error: 'll' was not declared in this scope
    4 | using pii = pair<ll, ll>;
      |                  ^~
timeismoney.cpp:4:22: error: 'll' was not declared in this scope
    4 | using pii = pair<ll, ll>;
      |                      ^~
timeismoney.cpp:4:24: error: template argument 1 is invalid
    4 | using pii = pair<ll, ll>;
      |                        ^
timeismoney.cpp:4:24: error: template argument 2 is invalid
timeismoney.cpp:5:20: error: 'll' was not declared in this scope
    5 | using Edge = array<ll, 5>;
      |                    ^~
timeismoney.cpp:5:25: error: template argument 1 is invalid
    5 | using Edge = array<ll, 5>;
      |                         ^
timeismoney.cpp:9:10: error: 'll' was not declared in this scope
    9 |   vector<ll> g;
      |          ^~
timeismoney.cpp:9:12: error: template argument 1 is invalid
    9 |   vector<ll> g;
      |            ^
timeismoney.cpp:9:12: error: template argument 2 is invalid
timeismoney.cpp:10:9: error: expected ')' before 'n'
   10 |   DSU(ll n) : g(n, -1) {}
      |      ~  ^~
      |         )
timeismoney.cpp:11:3: error: 'll' does not name a type
   11 |   ll find(ll a)
      |   ^~
timeismoney.cpp:18:14: error: 'll' has not been declared
   18 |   bool unite(ll a, ll b)
      |              ^~
timeismoney.cpp:18:20: error: 'll' has not been declared
   18 |   bool unite(ll a, ll b)
      |                    ^~
timeismoney.cpp: In member function 'bool DSU::unite(int, int)':
timeismoney.cpp:20:15: error: no matching function for call to 'find(int&)'
   20 |     a = find(a);
      |               ^
In file included from /usr/include/c++/10/bits/locale_facets.h:48,
                 from /usr/include/c++/10/bits/basic_ios.h:37,
                 from /usr/include/c++/10/ios:44,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from timeismoney.cpp:1:
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(std::istreambuf_iterator<_CharT>, std::istreambuf_iterator<_CharT>, const _CharT2&)'
  422 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note:   template argument deduction/substitution failed:
timeismoney.cpp:20:15: note:   mismatched types 'std::istreambuf_iterator<_CharT>' and 'int'
   20 |     a = find(a);
      |               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from timeismoney.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3894:5: note: candidate: 'template<class _IIter, class _Tp> _IIter std::find(_IIter, _IIter, const _Tp&)'
 3894 |     find(_InputIterator __first, _InputIterator __last,
      |     ^~~~
/usr/include/c++/10/bits/stl_algo.h:3894:5: note:   template argument deduction/substitution failed:
timeismoney.cpp:20:15: note:   candidate expects 3 arguments, 1 provided
   20 |     a = find(a);
      |               ^
timeismoney.cpp:21:15: error: no matching function for call to 'find(int&)'
   21 |     b = find(b);
      |               ^
In file included from /usr/include/c++/10/bits/locale_facets.h:48,
                 from /usr/include/c++/10/bits/basic_ios.h:37,
                 from /usr/include/c++/10/ios:44,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from timeismoney.cpp:1:
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(std::istreambuf_iterator<_CharT>, std::istreambuf_iterator<_CharT>, const _CharT2&)'
  422 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note:   template argument deduction/substitution failed:
timeismoney.cpp:21:15: note:   mismatched types 'std::istreambuf_iterator<_CharT>' and 'int'
   21 |     b = find(b);
      |               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from timeismoney.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3894:5: note: candidate: 'template<class _IIter, class _Tp> _IIter std::find(_IIter, _IIter, const _Tp&)'
 3894 |     find(_InputIterator __first, _InputIterator __last,
      |     ^~~~
/usr/include/c++/10/bits/stl_algo.h:3894:5: note:   template argument deduction/substitution failed:
timeismoney.cpp:21:15: note:   candidate expects 3 arguments, 1 provided
   21 |     b = find(b);
      |               ^
timeismoney.cpp:24:10: error: invalid types 'int[int]' for array subscript
   24 |     if (g[a] > g[b])
      |          ^
timeismoney.cpp:24:17: error: invalid types 'int[int]' for array subscript
   24 |     if (g[a] > g[b])
      |                 ^
timeismoney.cpp:26:6: error: invalid types 'int[int]' for array subscript
   26 |     g[a] += g[b];
      |      ^
timeismoney.cpp:26:14: error: invalid types 'int[int]' for array subscript
   26 |     g[a] += g[b];
      |              ^
timeismoney.cpp:27:6: error: invalid types 'int[int]' for array subscript
   27 |     g[b] = a;
      |      ^
timeismoney.cpp: At global scope:
timeismoney.cpp:32:6: error: 'pii' was not declared in this scope
   32 | pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
      |      ^~~
timeismoney.cpp:32:18: error: 'll' was not declared in this scope
   32 | pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
      |                  ^~
timeismoney.cpp:32:18: error: template argument 1 is invalid
timeismoney.cpp:32:18: error: template argument 2 is invalid
timeismoney.cpp:32:20: error: template argument 1 is invalid
   32 | pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
      |                    ^~
timeismoney.cpp:32:20: error: template argument 2 is invalid
timeismoney.cpp:32:31: error: 'll' was not declared in this scope
   32 | pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
      |                               ^~
timeismoney.cpp:32:44: error: 'Edge' was not declared in this scope
   32 | pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
      |                                            ^~~~
timeismoney.cpp:32:48: error: template argument 1 is invalid
   32 | pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
      |                                                ^
timeismoney.cpp:32:48: error: template argument 2 is invalid
timeismoney.cpp:32:51: error: 'edges' was not declared in this scope
   32 | pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
      |                                                   ^~~~~
timeismoney.cpp:32:65: error: 'll' was not declared in this scope
   32 | pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
      |                                                                 ^~
timeismoney.cpp:32:67: error: template argument 1 is invalid
   32 | pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
      |                                                                   ^
timeismoney.cpp:32:67: error: template argument 2 is invalid
timeismoney.cpp:32:70: error: 'weights' was not declared in this scope
   32 | pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
      |                                                                      ^~~~~~~
timeismoney.cpp:32:77: error: expression list treated as compound expression in initializer [-fpermissive]
   32 | pair<pii, vector<ll>> kruskal(ll n, vector<Edge> &edges, vector<ll> &weights)
      |                                                                             ^
timeismoney.cpp:53:1: error: 'll' does not name a type
   53 | ll cross(pii A, pii B, pii C)
      | ^~
timeismoney.cpp:60:1: error: 'll' does not name a type
   60 | ll main()
      | ^~