Submission #468025

#TimeUsernameProblemLanguageResultExecution timeMemory
468025czhang2718timeismoney (balkan11_timeismoney)C++17
100 / 100
983 ms560 KiB
#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; typedef long long ll; int n, m; pair<long long, 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){ if((ll)b.f*t[i]+b.s*c[i]!=(ll)b.f*t[j]+b.s*c[j]) return (ll)b.f*t[i]+b.s*c[i]<(ll)b.f*t[j]+b.s*c[j]; return t[i]<t[j]; // should be useless.. // return c[i]<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((ll)b.f*m.f+b.s*m.s==(ll)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; } int 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); answer(ans.s); } // n=200*256 // # CH vertices <= n^(3/4) // ~ 4e7
#Verdict Execution timeMemoryGrader output
Fetching results...