Submission #956922

#TimeUsernameProblemLanguageResultExecution timeMemory
956922bunhadasoutimeismoney (balkan11_timeismoney)C++14
100 / 100
109 ms1176 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define PB push_back #define EB emplace_back #define bit(n,i) ((n>>i)&1) #define all(x) x.begin(),x.end() #define ll long long #define sz(x) (int)x.size() #define TASK "cf" using namespace std; const double maxx=1e5; const int maxn=222; struct data{ ll u,v,t,c; double w; }; vector<data> e; int n,m; int par[maxn],Rank[maxn]; int find(int x) { if (x==par[x]) return x; return par[x]=find(par[x]); } bool UNION(int x,int y) { x=find(x);y=find(y); if (x==y) return 0; if (Rank[x]<Rank[y]) swap(x,y); Rank[x]+=Rank[y]; par[y]=x; return 1; } bool cmp(data a,data b) { return a.w<b.w; } void init(ll x){ for (int i=0;i<=n;i++) {par[i]=i;Rank[i]=1;} for (int i=0;i<m;i++) { e[i].w=e[i].c*x+e[i].t*(maxx-x); } sort(all(e),cmp); } ll solve(double mid) { init(mid); int solt=0,solc=0; for (int i=0;i<m;i++) { if (UNION(e[i].u,e[i].v)){ solt+=e[i].t; solc+=e[i].c; } } return 1ll*solc*solt; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; for (int i=1;i<=m;i++) { int u,v,x,y; cin>>u>>v>>x>>y; e.PB({u,v,x,y,0}); } double lo=0,hi=maxx; for (int rev=1;rev<=70;rev++) { double m1=(2*lo+hi)/3; double m2=(lo+2*hi)/3; if (solve(m1)<solve(m2)) hi=m2;else lo=m1; } init(lo); vector<pair<int,int>> ans; int sumc=0,sumt=0; for (int i=0;i<m;i++) { if (UNION(e[i].u,e[i].v)) { sumc+=e[i].c;sumt+=e[i].t; ans.PB(mp(e[i].u,e[i].v)); } } cout<<sumt<<" "<<sumc<<"\n"; for (auto x:ans) cout<<x.fi<<" "<<x.se<<"\n"; return 0; }

Compilation message (stderr)

timeismoney.cpp: In function 'int find(int)':
timeismoney.cpp:31:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   31 |     if (x==par[x]) return x; return par[x]=find(par[x]);
      |     ^~
timeismoney.cpp:31:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   31 |     if (x==par[x]) return x; return par[x]=find(par[x]);
      |                              ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...