Submission #480773

#	Time	Username	Problem	Language	Result	Execution time	Memory
480773		phamhoanghiep	timeismoney (balkan11_timeismoney)	C++14	100 / 100	1072 ms	680 KiB

timeismoney

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> ii;
typedef pair<ii,ii> iiii;
vector<iiii> edges;
vector<ii> rate;
const int bl=50;
const int maxn=202;
int n,m;
int a,b;
// MST: kruskal ??
int pset[maxn];
int sz[maxn];
int cnt_set;
void init() {
    for(int i=1 ; i<=n ; i++) {
        pset[i]=i;
        sz[i]=1;
    }
    cnt_set=n;
}
int find_set(int s) {
    if(s==pset[s]) return s;
    return pset[s]=find_set(pset[s]);
}
void union_set(int u, int v) {
    if(sz[u]>sz[v]) swap(u,v);
    pset[u]=v;
    sz[v]+=sz[u];
}
pair<int,int> solve() {
    init();
    int sum_t=0;
    int sum_c=0;
    for(iiii tmp: edges) {
        int u=tmp.fi.fi;
        int v=tmp.fi.se;
        int t=tmp.se.fi;
        int c=tmp.se.se;
        int fu=find_set(u);
        int fv=find_set(v);
        if(fu==fv) continue;
        else {
            union_set(fu,fv);
            sum_t+=t;
            sum_c+=c;
        }
    }
    return ii(sum_t,sum_c);
}
signed main() {
    for(int i=0 ; i<=bl ; i++) {
        for(int j=0 ; j<=bl ; j++) {
            if(i==0&&j==0) continue;
            if(__gcd(i,j)==1) {
                rate.push_back(ii(i,j));
            }
        }
    }
    cin>>n>>m;
    for(int i=1 ; i<=m ; i++) {
        int u,v,t,c;
        cin>>u>>v>>t>>c;
        u++; v++;
        edges.push_back(iiii(ii(u,v),ii(t,c)));
    }
    int finale=INT_MAX;
    int anst,ansc;
    ii X=ii(0,0);
    for(ii tmp: rate) {
        a=tmp.fi;
        b=tmp.se;
        sort(edges.begin(),edges.end(),[](const iiii &x, const iiii &y){return x.se.fi*a+x.se.se*b<y.se.fi*a+y.se.se*b;});
        ii res=solve();
        if(res.fi*res.se<finale) {
            finale=res.fi*res.se;
            anst=res.fi;
            ansc=res.se;
            X=ii(a,b);
        }
    }
    a=X.fi;
    b=X.se;
    cout<<anst<<' '<<ansc<<'\n';
    sort(edges.begin(),edges.end(),[](const iiii &x, const iiii &y){return x.se.fi*a+x.se.se*b<y.se.fi*a+y.se.se*b;});
    init();
    for(iiii tmp: edges) {
        int u=tmp.fi.fi;
        int v=tmp.fi.se;
        int t=tmp.se.fi;
        int c=tmp.se.se;
        int fu=find_set(u);
        int fv=find_set(v);
        if(fu==fv) continue;
        else {
            union_set(fu,fv);
            cout<<u-1<<' '<<v-1<<'\n';
        }
    }
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:92:13: warning: unused variable 't' [-Wunused-variable]
   92 |         int t=tmp.se.fi;
      |             ^
timeismoney.cpp:93:13: warning: unused variable 'c' [-Wunused-variable]
   93 |         int c=tmp.se.se;
      |             ^
timeismoney.cpp:86:28: warning: 'ansc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     cout<<anst<<' '<<ansc<<'\n';
      |                            ^~~~
timeismoney.cpp:86:17: warning: 'anst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     cout<<anst<<' '<<ansc<<'\n';
      |                 ^~~

• Subtask 1: 100 / 100