#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
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]))
{
t += e[2];
c += e[3];
mst.push_back(e[4]);
}
}
return {{t, c}, mst};
}
ll area(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;
}
int 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> best_MST;
pii best_V = {1e8, 1e8};
vector<ll> current_MST;
vector<ll> weights(M);
for (ll i = 0; i < M; i++)
{
weights[edges[i][4]] = edges[i][2];
}
pii A, B;
tie(A, best_MST) = kruskal(N, edges, weights);
best_V = A;
for (ll i = 0; i < M; i++)
{
weights[edges[i][4]] = edges[i][3];
}
tie(B, current_MST) = kruskal(N, edges, weights);
if ((ll)B.first * B.second < (ll)A.first * A.second)
{
best_V = B;
best_MST = current_MST;
}
stack<pair<pii, pii>> to_search;
to_search.push({A, B});
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;
tie(C, current_MST) = kruskal(N, edges, weights);
if (area(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";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
6 ms |
852 KB |
Output is correct |
| 9 |
Correct |
1 ms |
320 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
4 ms |
320 KB |
Output is correct |
| 15 |
Correct |
3 ms |
340 KB |
Output is correct |
| 16 |
Correct |
47 ms |
328 KB |
Output is correct |
| 17 |
Correct |
51 ms |
436 KB |
Output is correct |
| 18 |
Correct |
49 ms |
432 KB |
Output is correct |
| 19 |
Correct |
442 ms |
852 KB |
Output is correct |
| 20 |
Correct |
484 ms |
852 KB |
Output is correct |
