Submission #289700

#	Time	Username	Problem	Language	Result	Execution time	Memory
289700		ntfx	timeismoney (balkan11_timeismoney)	C++14	100 / 100	886 ms	904 KiB

timeismoney

/*
    Problem: https://oj.uz/problem/view/balkan11_timeismoney

    Solution: http://www.boi2011.ro/resurse/tasks/timeismoney-sol.pdf
*/
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
    #define D(a) cerr << #a << " = " << a << endl
#else 
    #define D(a) 8 
#endif
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define all(a) (a).begin(),(a).end()
#define dforn(i,n) dforsn(i,0,n)
#define forn(i,n) forsn(i,0,n)
#define si(a) int((a).size())
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first
#define endl '\n'
using pii = pair<int,int>;
using vi = vector<int>;
using ll = long long;

struct UF {
    vi par, sz;
    UF(int n): par(n), sz(n, 1) { iota(all(par), 0); }
    int find(int u) { return par[u] == u ? u : par[u] = find(par[u]); }
    bool connected(int u, int v) { return find(u) == find(v); }
    bool join(int u, int v) {
        if (connected(u, v)) return false;
        u = find(u), v = find(v);
        if (sz[u] < sz[v]) par[u] = v, sz[v] += sz[u];
        else par[v] = u, sz[u] += sz[v];
        return true;
    }
};

vi mst;
ll mn = 1e18;
int n, m, ba, bb, sumT, sumC;
vector<tuple<int,int,int,int>> edges;

struct Kruskal {
    vector<pii> ids;
    void addEdge(int cost, int id) { 
        ids.pb(cost, id); 
    }
    ll build() {
        sort(all(ids));
        mst.clear();
        UF uf(n);
        sumT = 0, sumC = 0;
        for (auto &[cst, id] : ids) {
            auto &[u, v, t, c] = edges[id];
            if (uf.join(u, v)) {
                mst.pb(id);
                sumT += t;
                sumC += c;
            }
        }
        ids.clear();
        return ll(sumT) * sumC;
    }
} kruskal;

struct Point {
    int x, y;
    bool collinear(const Point &p1, const Point &p2) {
        return ll(p2.y - p1.y) * (x - p1.x) == ll(y - p1.y) * (p2.x - p1.x);
    }
};
pii slope(const Point &p1, const Point &p2) {
    return {p1.y - p2.y, p1.x - p2.x};
}

// Minimize a * sumT + b * sumC = v
Point optimize(int a, int b) { 
    forn(i, m) {
        auto &[u, v, t, c] = edges[i];
        kruskal.addEdge(a*t + b*c, i);
    }
    ll val = kruskal.build();
    if (val < mn) {
        mn = val;
        ba = a, bb = b;
    }
    return {sumC, sumT};
}

void computeConvexHull(const Point &x, const Point &y) {
    auto [num, den] = slope(x, y);
    if (den < 0) den = -den;
    else if (num < 0) num = -num;
    Point z = optimize(den, num);
    if (z.collinear(x, y)) return;
    computeConvexHull(x, z);
    computeConvexHull(y, z);
}

int main() {
	fastio;
	
    cin >> n >> m;
    edges.resize(m);
    for (auto &[u, v, t, c] : edges)
        cin >> u >> v >> t >> c;

    computeConvexHull(optimize(0, 1), optimize(1, 0));

    optimize(ba, bb); 
    cout << sumT << ' ';
    cout << sumC << endl;
    for (int id : mst) {
        auto &[u, v, t, c] = edges[id];
        cout << u << ' ' << v << endl;
    }
	return 0;
}

Compilation message (stderr)

timeismoney.cpp: In member function 'll Kruskal::build()':
timeismoney.cpp:59:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for (auto &[cst, id] : ids) {
      |                    ^
timeismoney.cpp:60:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |             auto &[u, v, t, c] = edges[id];
      |                   ^
timeismoney.cpp: In function 'Point optimize(int, int)':
timeismoney.cpp:85:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |         auto &[u, v, t, c] = edges[i];
      |               ^
timeismoney.cpp: In function 'void computeConvexHull(const Point&, const Point&)':
timeismoney.cpp:97:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |     auto [num, den] = slope(x, y);
      |          ^
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:111:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |     for (auto &[u, v, t, c] : edges)
      |                ^
timeismoney.cpp:120:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |         auto &[u, v, t, c] = edges[id];
      |               ^

• Subtask 1: 100 / 100