#include <bits/stdc++.h>
#define CNT 202
#define fi first
#define se second
using namespace std;
struct pd {
int p1,p2,t,c;
pd() {}
pd(int p1,int p2,int t,int c):p1(p1),p2(p2),t(t),c(c) {}
bool operator< (pd o) const {
return (t*c)<(o.t*o.c);
}
};
int n,m;
int t1,t2,t3,t4,lines;
int height[CNT],root[CNT];
int t_sum,c_sum;
vector<pd > kr;
vector<int> ans;
int find(int p) {
if(root[p]==p) return p;
else return root[p]=find(root[p]);
}
void uni(int a,int b) {
a=find(a),b=find(b);
if(height[a]>height[b]) swap(a,b);
if(height[a]==height[b]) height[b]++;
root[a]=b;
}
int main() {
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
height[i]=1,root[i]=i;
for(int i=0;i<m;i++) {
scanf("%d %d %d %d",&t1,&t2,&t3,&t4);
kr.push_back(pd(t1,t2,t3,t4));
}
sort(kr.begin(),kr.end());
for(int i=0;lines<n-1;i++) {
auto now=kr[i];
if(find(now.p1)!=find(now.p2)) {
uni(now.p1,now.p2);
lines++;
ans.push_back(i);
t_sum+=now.t,c_sum+=now.c;
}
}
printf("%d %d\n",t_sum,c_sum);
for(auto i=ans.begin();i!=ans.end();i++)
printf("%d %d\n",kr[*i].p1,kr[*i].p2);
}
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:33:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
^
timeismoney.cpp:37:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&t1,&t2,&t3,&t4);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2160 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2488 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
2020 KB |
Output isn't correct |
| 11 |
Incorrect |
0 ms |
2020 KB |
Output isn't correct |
| 12 |
Incorrect |
0 ms |
2020 KB |
Output isn't correct |
| 13 |
Incorrect |
0 ms |
2020 KB |
Output isn't correct |
| 14 |
Incorrect |
0 ms |
2020 KB |
Output isn't correct |
| 15 |
Incorrect |
0 ms |
2020 KB |
Output isn't correct |
| 16 |
Incorrect |
0 ms |
2160 KB |
Output isn't correct |
| 17 |
Incorrect |
0 ms |
2160 KB |
Output isn't correct |
| 18 |
Incorrect |
0 ms |
2160 KB |
Output isn't correct |
| 19 |
Incorrect |
6 ms |
2488 KB |
Output isn't correct |
| 20 |
Incorrect |
6 ms |
2488 KB |
Output isn't correct |
