Submission #480773

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
480773	2021-10-18T03:28:04 Z	phamhoanghiep	timeismoney (balkan11_timeismoney)	C++14	100 / 100	1072 ms	680 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	2 ms	204 KB	Output is correct
4	Correct	4 ms	320 KB	Output is correct
5	Correct	17 ms	204 KB	Output is correct
6	Correct	13 ms	324 KB	Output is correct
7	Correct	81 ms	356 KB	Output is correct
8	Correct	425 ms	588 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	2 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	5 ms	204 KB	Output is correct
13	Correct	5 ms	204 KB	Output is correct
14	Correct	32 ms	204 KB	Output is correct
15	Correct	24 ms	328 KB	Output is correct
16	Correct	168 ms	360 KB	Output is correct
17	Correct	166 ms	332 KB	Output is correct
18	Correct	173 ms	352 KB	Output is correct
19	Correct	1039 ms	680 KB	Output is correct
20	Correct	1072 ms	588 KB	Output is correct