Submission #480755

#	Time	Username	Problem	Language	Result	Execution time	Memory
480755		phamhoanghiep	timeismoney (balkan11_timeismoney)	C++14	85 / 100	2081 ms	588 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=15;
const int maxn=202;
int n,m;
// 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;
}
void srt_edge(int a, int b) {
    for(int i=0 ; i<edges.size() ; i++) {
        for(int j=i+1 ; j<edges.size() ; j++) {
            int a1=edges[i].se.fi;
            int b1=edges[i].se.se;
            int a2=edges[j].se.fi;
            int b2=edges[j].se.se;
            if(a1*a+b1*b>a2*a+b2*b) swap(edges[i],edges[j]);
        }
    }
}
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(int a, int b) {
    srt_edge(a,b);
    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) {
        int a=tmp.fi;
        int b=tmp.se;
        ii res=solve(a,b);
        if(res.fi*res.se<finale) {
            finale=res.fi*res.se;
            anst=res.fi;
            ansc=res.se;
            X=ii(a,b);
        }
    }
    int a=X.fi;
    int b=X.se;
    cout<<anst<<' '<<ansc<<'\n';
    srt_edge(a,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 'void srt_edge(int, int)':
timeismoney.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0 ; i<edges.size() ; i++) {
      |                   ~^~~~~~~~~~~~~
timeismoney.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int j=i+1 ; j<edges.size() ; j++) {
      |                         ~^~~~~~~~~~~~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:102:13: warning: unused variable 't' [-Wunused-variable]
  102 |         int t=tmp.se.fi;
      |             ^
timeismoney.cpp:103:13: warning: unused variable 'c' [-Wunused-variable]
  103 |         int c=tmp.se.se;
      |             ^
timeismoney.cpp:96:28: warning: 'ansc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     cout<<anst<<' '<<ansc<<'\n';
      |                            ^~~~
timeismoney.cpp:96:17: warning: 'anst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     cout<<anst<<' '<<ansc<<'\n';
      |                 ^~~

• Subtask 1: 85 / 100