Submission #1029180

#TimeUsernameProblemLanguageResultExecution timeMemory
1029180lucritimeismoney (balkan11_timeismoney)C++17
45 / 100
2021 ms1220 KiB
#include <bits/stdc++.h> using namespace std; long long t[210],u[10010],v[10010],ti[10010],mo[10010],n,m,vmax=2000000000000000000,st,sm,p1,p2; long long sumt,summ; struct muchii{long long u,v,val,valt,valm;}a[10010]; long long tata(long long n) { if(t[n]==n)return n; return t[n]=tata(t[n]); } bool comp(muchii a,muchii b) { if(a.val!=b.val)return a.val<b.val; if(a.u!=b.u)return a.u<b.u; if(a.v!=b.v)return a.v<b.v; return a.valt<b.valt; } void calculeaza(long long v1,long long v2) { for(long long i=0;i<n;++i) t[i]=i; for(long long i=1;i<=m;++i) a[i]={u[i],v[i],ti[i]*v1+mo[i]*v2,ti[i],mo[i]}; sumt=summ=0; sort(a+1,a+m+1,comp); for(long long i=1;i<=m;++i) { if(tata(a[i].u)!=tata(a[i].v)) { t[t[a[i].u]]=t[a[i].v]; sumt+=a[i].valt; summ+=a[i].valm; } } } void scrie(long long v1,long long v2) { for(long long i=0;i<n;++i) t[i]=i; for(long long i=1;i<=m;++i) a[i]={u[i],v[i],ti[i]*v1+mo[i]*v2,ti[i],mo[i]}; sort(a+1,a+m+1,comp); for(long long i=1;i<=m;++i) { if(tata(a[i].u)!=tata(a[i].v)) { t[t[a[i].u]]=t[a[i].v]; cout<<a[i].u<<' '<<a[i].v<<'\n'; } } } int main() { cin>>n>>m; for(long long i=1;i<=m;++i) cin>>u[i]>>v[i]>>ti[i]>>mo[i]; for(long long i=0;i<=1000;++i) { calculeaza(i,1000); if(sumt*summ<vmax) { st=sumt,sm=summ; vmax=sumt*summ; p1=i; p2=1000; } calculeaza(1000,i); if(sumt*summ<vmax) { st=sumt,sm=summ; vmax=sumt*summ; p1=1000; p2=i; } } cout<<st<<' '<<sm<<'\n'; scrie(1,1); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...