Submission #956924

#	Time	Username	Problem	Language	Result	Execution time	Memory
956924		bunhadasou	timeismoney (balkan11_timeismoney)	C++14	100 / 100	136 ms	1428 KiB

timeismoney

#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;
const double eps=1e-9;


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,res;
    while(hi-lo>=eps){
        double m1=(2*lo+hi)/3;
        double m2=(lo+2*hi)/3;
        if (solve(m1)<solve(m2)) hi=m2;else {lo=m1;res=m1;}
    }
    init(res);
    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:32:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   32 |     if (x==par[x]) return x; return par[x]=find(par[x]);
      |     ^~
timeismoney.cpp:32:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   32 |     if (x==par[x]) return x; return par[x]=find(par[x]);
      |                              ^~~~~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:83:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |     init(res);
      |     ~~~~^~~~~

• Subtask 1: 100 / 100