#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define SIZE(x) (int)((x).size())
inline int readi(){
int x=0,f=1;char ch;ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct UnionFind {
vector<int> data;
void init(int n) { data.assign(n, -1); }
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
};
struct edge {
int x, y;
int time, cost;
};
int A, B;
vector<edge> E;
bool cmp(const edge &a, const edge &b){
return 1ll*a.time*A + 1ll*a.cost*B < 1ll*b.time*A + 1ll*b.cost*B;
}
ll cross(pii O, pii A, pii B){
return 1ll*(A.first-O.first)*(B.second-O.second) - 1ll*(A.second-O.second)*(B.first-O.first);
}
int N, M;
vector<pii> lower_hull;
vector<pii> slopes;
vector<pii> ans;
pii bestmst;
pii mst(int a, int b, bool save) {
assert(a>=0 && b>=0);
A=a, B=b;
sort(E.begin(),E.end(),cmp);
UnionFind uf;
uf.init(N);
pii res = {0,0};
for(int i=0; i<M; i++){
if(uf.unionSet(E[i].x, E[i].y)){
res.first += E[i].time;
res.second += E[i].cost;
if(save) ans.emplace_back(E[i].x, E[i].y);
}
}
lower_hull.push_back(res);
slopes.emplace_back(a,b);
if(save) bestmst=res;
return res;
}
void go(pii a, pii b) {
pii p = mst(a.second-b.second,b.first-a.first,0);
if(cross(p,a,b)==0) return;
go(a,p); go(p,b);
}
int main() {
N = readi();
M = readi();
E.resize(M);
for(int i=0; i<M; i++){
E[i].x = readi();
E[i].y = readi();
E[i].time = readi();
E[i].cost = readi();
}
pii a = mst(1,0,0);
pii b = mst(0,1,0);
go(a, b);
ll res = 1e18;
for(pii p : lower_hull){
res = min(res, p.first*p.second);
}
for(int i=0; i<SIZE(lower_hull); i++){
if(lower_hull[i].first*lower_hull[i].second==res){
mst(slopes[i].first, slopes[i].second, 1);
break;
}
}
printf("%lld %lld\n",bestmst.first,bestmst.second);
for(pii p : ans){
printf("%lld %lld\n",p.first,p.second);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2180 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 11 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 12 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 14 |
Correct |
6 ms |
2020 KB |
Output is correct |
| 15 |
Correct |
3 ms |
2020 KB |
Output is correct |
| 16 |
Correct |
96 ms |
2164 KB |
Output is correct |
| 17 |
Correct |
103 ms |
2164 KB |
Output is correct |
| 18 |
Correct |
96 ms |
2164 KB |
Output is correct |
| 19 |
Correct |
886 ms |
2312 KB |
Output is correct |
| 20 |
Correct |
916 ms |
2312 KB |
Output is correct |
