#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long
#define inf 1000000009
#define md 1000000007
#define li 10005
#define mp make_pair
#define pb push_back
#define mid (l+r)/2
#define pi pair<int, pair<int, pair<int,int> > >
using namespace std;
int n,m,x,y,t,r1=256,r2,fa[205],mn=inf,tutty,mm,tutty2;
int sz[205];
pair<int, pair<int, pair<int,int> > > p[li];
vector< pair<int,int> > ans;
pair<int,int> son;
bool cmp(pi a,pi b){
return r1*a.se.se.fi+r2*a.se.se.se<r1*b.se.se.fi+r2*b.se.se.se;
}
int dsu(int x){
if(fa[x]==x) return x;
return fa[x]=dsu(fa[x]);
}
pair<int,int> solve(){
//printf("(");
ans.clear();
for(int i=0;i<n;i++) {fa[i]=i;sz[i]=1;}
sort(p+1,p+m+1,cmp);
int totalt=0,totalp=0;
for(int i=1;i<=m;i++){
int seh1=p[i].fi;
int seh2=p[i].se.fi;
int tm=p[i].se.se.fi;
int pr=p[i].se.se.se;
if(dsu(seh1)!=dsu(seh2)){
seh1=dsu(seh1);
seh2=dsu(seh2);
if(sz[seh1]<sz[seh2]) swap(seh1,seh2);
totalt+=tm;
totalp+=pr;
sz[seh1]+=sz[seh2];
fa[seh2]=seh1;
ans.pb(mp(seh1,seh2));
}
}
return mp(totalt,totalp);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d %d %d %d",&x,&y,&t,&mm);
//printf("?");
p[i]=mp(x,mp(y,mp(t,mm)));
}
//printf("?");
for(int i=1;i<=256;i++){
r2=i;
pair<int,int> tmp=solve();
if(tmp.fi*tmp.se<mn){
mn=tmp.fi*tmp.se;
son=tmp;
}
}
r2=256;
for(int i=1;i<=256;i++){
r1=i;
pair<int,int> tmp=solve();
if(tmp.fi*tmp.se<mn){
mn=tmp.fi*tmp.se;
son=tmp;
}
}
printf("%d %d\n",son.fi,son.se);
for(int i=0;i<(int)ans.size();i++){
printf("%d %d\n",ans[i].fi,ans[i].se);
}
return 0;
}
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
timeismoney.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&x,&y,&t,&mm);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
504 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
516 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
752 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
752 KB |
Output isn't correct |
| 5 |
Incorrect |
16 ms |
752 KB |
Output isn't correct |
| 6 |
Incorrect |
13 ms |
752 KB |
Output isn't correct |
| 7 |
Incorrect |
73 ms |
752 KB |
Output isn't correct |
| 8 |
Incorrect |
365 ms |
1072 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
1072 KB |
Output isn't correct |
| 10 |
Incorrect |
4 ms |
1072 KB |
Output isn't correct |
| 11 |
Incorrect |
3 ms |
1072 KB |
Output isn't correct |
| 12 |
Incorrect |
5 ms |
1072 KB |
Output isn't correct |
| 13 |
Incorrect |
5 ms |
1072 KB |
Output isn't correct |
| 14 |
Incorrect |
18 ms |
1072 KB |
Output isn't correct |
| 15 |
Incorrect |
14 ms |
1120 KB |
Output isn't correct |
| 16 |
Incorrect |
99 ms |
1256 KB |
Output isn't correct |
| 17 |
Incorrect |
134 ms |
1256 KB |
Output isn't correct |
| 18 |
Incorrect |
100 ms |
1256 KB |
Output isn't correct |
| 19 |
Incorrect |
646 ms |
1512 KB |
Output isn't correct |
| 20 |
Incorrect |
607 ms |
1748 KB |
Output isn't correct |
