| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1302655 | vlomaczk | 시간이 돈 (balkan11_timeismoney) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct Edge {
ll a, b, t, m;
};
vector<Edge> edges;
vector<ll> rep, sajz;
ll Find(ll v) {
return (rep[v]==v ? v : rep[v] = Find(rep[v]));
}
bool Union(ll a, ll b) {
a = Find(a);
b = Find(b);
if(a==b) return 0;
if(sajz[b] > sajz[a]) swap(a,b);
rep[b] = a;
sajz[a] += sajz[b];
return 1;
}
vector<Edge> res;
pair<ll, ll> mst(ll wsp1, ll wsp2) {
while(res.size()) res.pop_back();
for(ll i=0; i<M; ++i) rep[i] = i;
for(ll i=0; i<M; ++i) sajz[i] = 1;
ll time = 0;
ll money = 0;
sort(edges.begin(), edges.end(), [&](Edge x, Edge y) {
ll v1 = wsp1*x.t + wsp2*x.m;
ll v2 = wsp1*y.t + wsp2*y.m;
return v1 < v2;
});
for(auto[a,b,t,m] : edges) {
if(Union(a,b)) {
time += t;
money += m;
res.push_back({a,b,t,m});
}
}
return {time, money};
}
pair<ll, pair<ll, ll>> rek(ll x1, ll y1, ll x2, ll y2) {
ll a = y2-y1;
ll b = x1-x2;
auto[t,m] = mst(a,b);
if(a*t + b*m == a*x1 + b*y1) return {t*m, {a,b}};
pair<ll, pair<ll, ll>> a1 = rek(x1,y1,t,m);
pair<ll, pair<ll, ll>> a2 = rek(t,m,x2,y2);
return min(min(a1,a2), {t*m, {a,b}});
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n, e;
cin >> n >> e;
for(ll i=0; i<e; ++i) {
ll a, b, m, t;
cin >> a >> b >> t >> m;
edges.push_back({a,b,t,m});
}
rep.assign(n,0);
sajz.assign(n,0);
auto[t1,m1] = mst(0,1);
auto[t2,m2] = mst(1,0);
pair<ll, pair<ll, ll>> ans = rek(t1,m1,t2,m2);
ans = min(ans, {t1*m1, {0,1}});
ans = min(ans, {t2*m2, {1,0}});
auto[val, para] = ans;
auto[a,b] = para;
auto[t,m] = mst(a,b);
cout << t << " " << m << "\n";
for(auto[a,b,t,m] : res) cout << a << " " << b << "\n";
return 0;
}