Submission #1264163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264163		VMaksimoski008	timeismoney (balkan11_timeismoney)	C++20	Compilation error	0 ms	0 KiB

timeismoney

v#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e9;
const int N = 1e5 + 5;

struct union_find {
    int n;
    vector<int> par, size;

    union_find(int _n) : n(_n), par(n+1), size(n+1, 1) {
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int u) {
        if(u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    bool uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return 0;
        if(size[a] < size[b]) swap(a, b);
        size[a] += size[b];
        par[b] = a;
        return 1;
    }
};

struct point {
    ll x, y;
    bool operator<(const point &b) {
        return x * y < b.x * b.y;
    }
};

long double slope(const point &a, const point &b) {
    assert(b.x != a.x);
    return (b.y - a.y) / (b.x - a.x);
}

ll area(const point &a, const point &b, const point &c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int n, m;
vector<ar<int, 4> > edg;
vector<pii> used;

point mst(ll A, ll B) {
    ll T=0, C=0;
    union_find dsu(n);

    sort(edg.begin(), edg.end(), [&](const ar<int, 4> &x, const ar<int, 4> &y) {
        return A * x[2] + B * x[3] <= A * y[2] + B * y[3]; 
    });

    used.clear();
    for(auto [a, b, t, c] : edg) {
        if(dsu.uni(a, b)) {
            T += t;
            C += c;
            used.push_back({ a, b });
        }
    }
    return { T, C };
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    cin >> n >> m;
    while(m--) {
        int a, b, t, c;
        cin >> a >> b >> t >> c;
        edg.push_back({ a, b, t, c });
    }

    point ans = { inf, inf };
    vector<pii> to_print;
    point byT = mst(1, 0), byC = mst(0, 1);
    
    if(byT < ans) ans = byT, to_print = used;
    if(byC < ans) ans = byC, to_print = used;

    stack<pair<point, point> > st;
    st.push({ byT, byC });

    while(!st.empty()) {
        auto [tl, br] = st.top(); st.pop();

        point nxt = mst(-(br.y - tl.y), br.x - tl.x);
        if(area(tl, br, nxt) >= 0) continue;

        if(nxt < ans) {
            ans = nxt;
            to_print = used;
        }

        st.push({ tl, nxt });
        st.push({ nxt, br });
    }

    cout << ans.x << " " << ans.y << '\n';
    for(auto [a, b] : to_print)
        cout << a << " " << b << '\n';
}

Compilation message (stderr)

timeismoney.cpp:1:2: error: stray '#' in program
    1 | v#include <bits/stdc++.h>
      |  ^
timeismoney.cpp:1:1: error: 'v' does not name a type
    1 | v#include <bits/stdc++.h>
      | ^
timeismoney.cpp:8:13: error: 'pair' does not name a type; did you mean 'ar'?
    8 | using pii = pair<int, int>;
      |             ^~~~
      |             ar
timeismoney.cpp:9:13: error: 'pair' does not name a type; did you mean 'ar'?
    9 | using pll = pair<ll, ll>;
      |             ^~~~
      |             ar
timeismoney.cpp:17:5: error: 'vector' does not name a type
   17 |     vector<int> par, size;
      |     ^~~~~~
timeismoney.cpp: In constructor 'union_find::union_find(int)':
timeismoney.cpp:19:33: error: class 'union_find' does not have any field named 'par'
   19 |     union_find(int _n) : n(_n), par(n+1), size(n+1, 1) {
      |                                 ^~~
timeismoney.cpp:19:43: error: class 'union_find' does not have any field named 'size'
   19 |     union_find(int _n) : n(_n), par(n+1), size(n+1, 1) {
      |                                           ^~~~
timeismoney.cpp:20:33: error: 'par' was not declared in this scope; did you mean 'ar'?
   20 |         for(int i=1; i<=n; i++) par[i] = i;
      |                                 ^~~
      |                                 ar
timeismoney.cpp: In member function 'int union_find::find(int)':
timeismoney.cpp:24:17: error: 'par' was not declared in this scope; did you mean 'ar'?
   24 |         if(u == par[u]) return u;
      |                 ^~~
      |                 ar
timeismoney.cpp:25:16: error: 'par' was not declared in this scope; did you mean 'ar'?
   25 |         return par[u] = find(par[u]);
      |                ^~~
      |                ar
timeismoney.cpp: In member function 'bool union_find::uni(int, int)':
timeismoney.cpp:31:12: error: 'size' was not declared in this scope
   31 |         if(size[a] < size[b]) swap(a, b);
      |            ^~~~
timeismoney.cpp:31:31: error: 'swap' was not declared in this scope
   31 |         if(size[a] < size[b]) swap(a, b);
      |                               ^~~~
timeismoney.cpp:32:9: error: 'size' was not declared in this scope
   32 |         size[a] += size[b];
      |         ^~~~
timeismoney.cpp:33:9: error: 'par' was not declared in this scope; did you mean 'ar'?
   33 |         par[b] = a;
      |         ^~~
      |         ar
timeismoney.cpp: In function 'long double slope(const point&, const point&)':
timeismoney.cpp:46:5: error: 'assert' was not declared in this scope
   46 |     assert(b.x != a.x);
      |     ^~~~~~
timeismoney.cpp:1:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
  +++ |+#include <cassert>
    1 | v#include <bits/stdc++.h>
timeismoney.cpp: At global scope:
timeismoney.cpp:2:12: error: 'array' was not declared in this scope
    2 | #define ar array
      |            ^~~~~
timeismoney.cpp:55:8: note: in expansion of macro 'ar'
   55 | vector<ar<int, 4> > edg;
      |        ^~
timeismoney.cpp:2:12: error: 'array' was not declared in this scope
    2 | #define ar array
      |            ^~~~~
timeismoney.cpp:55:8: note: in expansion of macro 'ar'
   55 | vector<ar<int, 4> > edg;
      |        ^~
timeismoney.cpp:2:12: error: 'array' was not declared in this scope
    2 | #define ar array
      |            ^~~~~
timeismoney.cpp:55:8: note: in expansion of macro 'ar'
   55 | vector<ar<int, 4> > edg;
      |        ^~
timeismoney.cpp:2:12: error: 'array' was not declared in this scope
    2 | #define ar array
      |            ^~~~~
timeismoney.cpp:55:8: note: in expansion of macro 'ar'
   55 | vector<ar<int, 4> > edg;
      |        ^~
timeismoney.cpp:2:12: error: 'array' was not declared in this scope
    2 | #define ar array
      |            ^~~~~
timeismoney.cpp:55:8: note: in expansion of macro 'ar'
   55 | vector<ar<int, 4> > edg;
      |        ^~
timeismoney.cpp:2:12: error: 'array' was not declared in this scope
    2 | #define ar array
      |            ^~~~~
timeismoney.cpp:55:8: note: in expansion of macro 'ar'
   55 | vector<ar<int, 4> > edg;
      |        ^~
timeismoney.cpp:2:12: error: 'array' was not declared in this scope
    2 | #define ar array
      |            ^~~~~
timeismoney.cpp:55:8: note: in expansion of macro 'ar'
   55 | vector<ar<int, 4> > edg;
      |        ^~
timeismoney.cpp:2:12: error: 'array' was not declared in this scope
    2 | #define ar array
      |            ^~~~~
timeismoney.cpp:55:8: note: in expansion of macro 'ar'
   55 | vector<ar<int, 4> > edg;
      |        ^~
timeismoney.cpp:2:12: error: 'array' was not declared in this scope
    2 | #define ar array
      |            ^~~~~
timeismoney.cpp:55:8: note: in expansion of macro 'ar'
   55 | vector<ar<int, 4> > edg;
      |        ^~
timeismoney.cpp:55:1: error: 'vector' does not name a type
   55 | vector<ar<int, 4> > edg;
      | ^~~~~~
timeismoney.cpp:56:8: error: 'pii' was not declared in this scope
   56 | vector<pii> used;
      |        ^~~
timeismoney.cpp:56:8: error: 'pii' was not declared in this scope
timeismoney.cpp:56:8: error: 'pii' was not declared in this scope
timeismoney.cpp:56:8: error: 'pii' was not declared in this scope
timeismoney.cpp:56:8: error: 'pii' was not declared in this scope
timeismoney.cpp:56:8: error: 'pii' was not declared in this scope
timeismoney.cpp:56:8: error: 'pii' was not declared in this scope
timeismoney.cpp:56:8: error: 'pii' was not declared in this scope
timeismoney.cpp:56:8: error: 'pii' was not declared in this scope
timeismoney.cpp:56:1: error: 'vector' does not name a type
   56 | vector<pii> used;
      | ^~~~~~
timeismoney.cpp: In function 'point mst(ll, ll)':
timeismoney.cpp:62:10: error: 'edg' was not declared in this scope
   62 |     sort(edg.begin(), edg.end(), [&](const ar<int, 4> &x, const ar<int, 4> &y) {
      |          ^~~
timeismoney.cpp:2:12: error: 'array' does not name a type
    2 | #define ar array
      |            ^~~~~
timeismoney.cpp:62:44: note: in expansion of macro 'ar'
   62 |     sort(edg.begin(), edg.end(), [&](const ar<int, 4> &x, const ar<int, 4> &y) {
      |                                            ^~
timeismoney.cpp: In lambda function:
timeismoney.cpp:64:7: error: expected '{' before ';' token
   64 |     });
      |       ^
timeismoney.cpp: In function 'point mst(ll, ll)':
timeismoney.cpp:64:7: error: expected ')' before ';' token
   64 |     });
      |       ^
      |       )
timeismoney.cpp:62:9: note: to match this '('
   62 |     sort(edg.begin(), edg.end(), [&](const ar<int, 4> &x, const ar<int, 4> &y) {
      |         ^
timeismoney.cpp:66:5: error: 'used' was not declared in this scope
   66 |     used.clear();
      |     ^~~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:78:5: error: 'ios_base' has not been declared
   78 |     ios_base::sync_with_stdio(false);
      |     ^~~~~~~~
timeismoney.cpp:79:5: error: 'cout' was not declared in this scope
   79 |     cout.tie(0); cin.tie(0);
      |     ^~~~
timeismoney.cpp:79:18: error: 'cin' was not declared in this scope
   79 |     cout.tie(0); cin.tie(0);
      |                  ^~~
timeismoney.cpp:85:9: error: 'edg' was not declared in this scope
   85 |         edg.push_back({ a, b, t, c });
      |         ^~~
timeismoney.cpp:89:12: error: 'pii' was not declared in this scope
   89 |     vector<pii> to_print;
      |            ^~~
timeismoney.cpp:89:5: error: 'vector' was not declared in this scope
   89 |     vector<pii> to_print;
      |     ^~~~~~
timeismoney.cpp:89:17: error: 'to_print' was not declared in this scope
   89 |     vector<pii> to_print;
      |                 ^~~~~~~~
timeismoney.cpp:92:41: error: 'used' was not declared in this scope
   92 |     if(byT < ans) ans = byT, to_print = used;
      |                                         ^~~~
timeismoney.cpp:93:41: error: 'used' was not declared in this scope
   93 |     if(byC < ans) ans = byC, to_print = used;
      |                                         ^~~~
timeismoney.cpp:95:11: error: 'pair' was not declared in this scope
   95 |     stack<pair<point, point> > st;
      |           ^~~~
timeismoney.cpp:95:5: error: 'stack' was not declared in this scope
   95 |     stack<pair<point, point> > st;
      |     ^~~~~
timeismoney.cpp:95:21: error: expected primary-expression before ',' token
   95 |     stack<pair<point, point> > st;
      |                     ^
timeismoney.cpp:95:28: error: expected primary-expression before '>' token
   95 |     stack<pair<point, point> > st;
      |                            ^
timeismoney.cpp:95:30: error: expected primary-expression before '>' token
   95 |     stack<pair<point, point> > st;
      |                              ^
timeismoney.cpp:95:32: error: 'st' was not declared in this scope; did you mean 'std'?
   95 |     stack<pair<point, point> > st;
      |                                ^~
      |                                std
timeismoney.cpp:106:24: error: 'used' was not declared in this scope
  106 |             to_print = used;
      |                        ^~~~