# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
467999 | czhang2718 | timeismoney (balkan11_timeismoney) | C++17 | 829 ms | 744 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define nl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
typedef pair<int, int> pii;
typedef vector<int> vi;
#define int long long
int n, m;
pair<int, pii> ans;
vi edges;
const int N=200;
const int M=10000;
int u[M], v[M], t[M], c[M];
int par[N];
pii b;
int find(int x){
if(par[x]==x) return x;
return par[x]=find(par[x]);
}
bool join(int x, int y){
int a=find(x);
int b=find(y);
if(a==b) return 0;
par[a]=b;
return 1;
}
bool comp(int i, int j){
return b.f*t[i]+b.s*c[i]<b.f*t[j]+b.s*c[j];
}
pii get_min(pii bb){
b=bb;
sort(edges.begin(), edges.end(), comp);
for(int i=0; i<n; i++) par[i]=i;
pii ret={0, 0};
for(int e:edges){
if(join(u[e], v[e])){
ret.f+=t[e];
ret.s+=c[e];
}
}
return ret;
}
void search(pii l, pii r){
pii bb={-(r.s-l.s), r.f-l.f};
pii m=get_min(bb);
ans=min(ans, {m.f*m.s, bb});
if(b.f*m.f+b.s*m.s==b.f*l.f+b.s*l.s) return;
search(l, m);
search(m, r);
}
void answer(pii bb){
b=bb;
sort(edges.begin(), edges.end(), comp);
for(int i=0; i<n; i++) par[i]=i;
pii ret={0, 0};
vi use;
for(int e:edges){
if(join(u[e], v[e])){
ret.f+=t[e];
ret.s+=c[e];
use.pb(e);
}
}
cout << ret.f << " " << ret.s << nl;
for(int i:use) cout << u[i] << " " << v[i] << nl;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
cin >> n >> m;
for(int i=0; i<m; i++){
cin >> u[i] >> v[i] >> t[i] >> c[i];
edges.pb(i);
}
pii l=get_min({1, 0});
pii r=get_min({0, 1});
ans=min(mp(l.f*l.s, mp(1, 0)), mp(r.f*r.s, mp(0, 1)));
search(l, r);
// cout << "best slope " << ans.s.f << " " << ans.s.s << nl;
answer(ans.s);
}
// n=200*256
// # CH vertices <= n^(3/4)
// ~ 4e7
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |