#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=20;
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
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';
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
204 KB |
Output is correct |
| 5 |
Correct |
36 ms |
204 KB |
Output is correct |
| 6 |
Correct |
22 ms |
204 KB |
Output is correct |
| 7 |
Correct |
832 ms |
336 KB |
Output is correct |
| 8 |
Execution timed out |
2079 ms |
588 KB |
Time limit exceeded |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
2 ms |
204 KB |
Output is correct |
| 13 |
Correct |
3 ms |
204 KB |
Output is correct |
| 14 |
Correct |
47 ms |
204 KB |
Output is correct |
| 15 |
Correct |
29 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1047 ms |
336 KB |
Output is correct |
| 17 |
Correct |
1050 ms |
344 KB |
Output is correct |
| 18 |
Correct |
1051 ms |
344 KB |
Output is correct |
| 19 |
Execution timed out |
2074 ms |
640 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2061 ms |
588 KB |
Time limit exceeded |
