#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<unordered_map>
#include <set>
#define ll long long
#define For(i, n) for(ll i = 0; i < n; i++)
#define ffor(i, a, n) for(ll i = a; i < n; i++)
#define rfor(i, n) for(ll i = n; i >= 0; i--)
#define rffor(i, a, n) for(ll i = n; i >= a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 1e18
#define mod (1e9 + 7)
#define rsz resize
#define prv 47
using namespace std;
ll mini = NEK;
ll minit = 1000000000;
ll minic = 1000000000;
vec<ll> odp;
vec<ll> odp_lok;
ll n;
struct hrana{
ll x, y, t, c;
};
vec<hrana> h_pov;
struct tr {
ll x, y, w, ind;
};
bool zorad(tr a, tr b) {
return a.w < b.w;
}
ll otec(ll x, vec<ll>&o) {
if (o[x] == x) return x;
return o[x] = otec(o[x], o);
}
pii kruskal(ll k1, ll k2) {
vec<ll> o(n);
For(i, n) o[i] = i;
vec<tr> h;
ll m = h_pov.size();
For(i, m) {
h.push_back({ h_pov[i].x, h_pov[i].y, h_pov[i].c * k2 - h_pov[i].t * k1, i });
}
sort(h.begin(), h.end(), zorad);
ll val = 0;
ll suc_t = 0;
ll suc_c = 0;
For(i, m) {
if (otec(h[i].x, o) == otec(h[i].y, o)) continue;
val += h[i].w;
suc_t += h_pov[h[i].ind].t;
suc_c += h_pov[h[i].ind].c;
o[otec(h[i].x, o)] = otec(h[i].y, o);
odp_lok.push_back(h[i].ind);
}
return { suc_t, suc_c };
}
void divide(pii a, pii b) {
ll k1 = b.ss - a.ss;
ll k2 = b.ff - a.ff;
pii c = kruskal(k1, k2);
if (((b.ff - a.ff) * (c.ss - a.ss) - (b.ss - a.ss) * (c.ff - a.ff)) > 0 || ((c.ff == a.ff) && (c.ss == a.ss)) || ((c.ff == b.ff) && (c.ss == b.ss))) {
odp_lok.clear();
return;
}
if (mini > c.ff * c.ss) {
mini = c.ff * c.ss;
minit = c.ff;
minic = c.ss;
odp.clear();
for (auto i : odp_lok) odp.push_back(i);
}
odp_lok.clear();
divide(a, c);
divide(c, b);
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//ifstream cin("curling.in");
//ofstream cout("curling.out");
cin >> n;
ll m;
cin >> m;
For(i, m) {
ll x, y, t, c;
cin >> x >> y >> t >> c;
h_pov.push_back({ x, y, t, c });
}
pii a = kruskal(-1, 0);
if (mini > a.ff * a.ss) {
mini = a.ff * a.ss;
minit = a.ff;
minic = a.ss;
odp.clear();
for (auto i : odp_lok) odp.push_back(i);
}
odp_lok.clear();
pii b = kruskal(0, 1);
if (mini > b.ff * b.ss) {
mini = b.ff * b.ss;
minit = b.ff;
minic = b.ss;
odp.clear();
for (auto i : odp_lok) odp.push_back(i);
}
odp_lok.clear();
divide(a, b);
cout << minit << ' ' << minic << '\n';
for (auto i : odp) cout << h_pov[i].x << ' ' << h_pov[i].y << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
516 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1568 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
8 ms |
516 KB |
Output is correct |
| 15 |
Correct |
5 ms |
348 KB |
Output is correct |
| 16 |
Correct |
134 ms |
660 KB |
Output is correct |
| 17 |
Correct |
136 ms |
660 KB |
Output is correct |
| 18 |
Correct |
127 ms |
600 KB |
Output is correct |
| 19 |
Correct |
1326 ms |
1880 KB |
Output is correct |
| 20 |
Correct |
1349 ms |
2416 KB |
Output is correct |
