/*
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;
int n, m, A, B;
ll mn = 1e18, 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 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);
}
};
// 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 v = kruskal.build();
if (v < mn) mn = v, A = a, B = b;
return {sumC, sumT};
}
void computeConvexHull(const Point &p1, const Point &p2) {
Point p = optimize(p2.x - p1.x, p1.y - p2.y);
if (p.collinear(p1, p2)) return;
computeConvexHull(p1, p), computeConvexHull(p, p2);
}
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(A, B);
cout << sumT << ' ' << sumC << endl;
for (int id : mst) {
auto &[u, v, t, c] = edges[id];
cout << u << ' ' << v << endl;
}
return 0;
}
Compilation message
timeismoney.cpp: In member function 'll Kruskal::build()':
timeismoney.cpp:57:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
57 | for (auto &[cst, id] : ids) {
| ^
timeismoney.cpp:58:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | auto &[u, v, t, c] = edges[id];
| ^
timeismoney.cpp: In function 'Point optimize(int, int)':
timeismoney.cpp:77:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | auto &[u, v, t, c] = edges[i];
| ^
timeismoney.cpp:82:13: warning: narrowing conversion of 'sumC' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
82 | return {sumC, sumT};
| ^~~~
timeismoney.cpp:82:19: warning: narrowing conversion of 'sumT' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
82 | return {sumC, sumT};
| ^~~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:96:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
96 | for (auto &[u, v, t, c] : edges)
| ^
timeismoney.cpp:104:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
104 | auto &[u, v, t, c] = edges[id];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
8 ms |
896 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
6 ms |
384 KB |
Output is correct |
| 15 |
Correct |
4 ms |
384 KB |
Output is correct |
| 16 |
Correct |
98 ms |
384 KB |
Output is correct |
| 17 |
Correct |
102 ms |
384 KB |
Output is correct |
| 18 |
Correct |
95 ms |
384 KB |
Output is correct |
| 19 |
Correct |
865 ms |
896 KB |
Output is correct |
| 20 |
Correct |
881 ms |
896 KB |
Output is correct |
