#include <bits/stdc++.h>
using namespace std;
int n,m;
struct Edge {
int s,e,t,c;
};
Edge edge[10000];
int one,two;
bool comp(Edge a,Edge b) {
return one*a.t+two*a.c<one*b.t+two*b.c;
}
int opt1=-1;
int opt2=-1;
long long ret1=1e6;
long long ret2=1e6;
int p[200];
int find(int a) {
if (p[a]<0) {
return a;
}
p[a]=find(p[a]);
return p[a];
}
void merge(int a,int b) {
a=find(a);
b=find(b);
if (a==b) {
return;
}
p[b]=a;
}
void solve(int x1,int y1,int x2,int y2) {
if (x1==x2&&y1==y2) {
return;
}
one=y1-y2;
two=x2-x1;
int x=0;
int y=0;
sort(edge,edge+m,comp);
memset(p,-1,sizeof(p));
for(int i=0;i<m;i++) {
if (find(edge[i].s)!=find(edge[i].e)) {
x+=edge[i].t;
y+=edge[i].c;
merge(edge[i].s,edge[i].e);
}
}
if ((long long)x*(long long)y<ret1*ret2) {
ret1=x;
ret2=y;
opt1=y1-y2;
opt2=x2-x1;
}
if ((x!=x2)||(y!=y2))
solve(x1,y1,x,y);
if (x!=x1||y!=y1)
solve(x,y,x2,y2);
}
int main(void) {
scanf("%d %d\n",&n,&m);
for(int i=0;i<m;i++) {
scanf("%d %d %d %d\n",&edge[i].s,&edge[i].e,&edge[i].t,&edge[i].c);
}
one=1;
two=0;
int x1=0;
int x2=0;
int y1=0;
int y2=0;
sort(edge,edge+m,comp);
memset(p,-1,sizeof(p));
for(int i=0;i<m;i++) {
if (find(edge[i].s)!=find(edge[i].e)) {
x1+=edge[i].t;
y1+=edge[i].c;
merge(edge[i].s,edge[i].e);
}
}
if (x1*(long long)y1<ret1*ret2) {
ret1=x1;
ret2=y1;
opt1=1;
opt2=0;
}
one=0;
two=1;
sort(edge,edge+m,comp);
memset(p,-1,sizeof(p));
for(int i=0;i<m;i++) {
if (find(edge[i].s)!=find(edge[i].e)) {
x2+=edge[i].t;
y2+=edge[i].c;
merge(edge[i].s,edge[i].e);
}
}
if (x2*(long long)y2<ret1*ret2) {
ret1=x1;
ret2=y1;
opt1=0;
opt2=1;
}
solve(x1,y1,x2,y2);
printf("%d %d\n",ret1,ret2);
one=opt1;
two=opt2;
sort(edge,edge+m,comp);
memset(p,-1,sizeof(p));
for(int i=0;i<m;i++) {
if (find(edge[i].s)!=find(edge[i].e)) {
merge(edge[i].s,edge[i].e);
printf("%d %d\n",edge[i].s,edge[i].e);
}
}
}
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:114:31: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
printf("%d %d\n",ret1,ret2);
^
timeismoney.cpp:114:31: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
timeismoney.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d\n",&n,&m);
~~~~~^~~~~~~~~~~~~~~~~
timeismoney.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d\n",&edge[i].s,&edge[i].e,&edge[i].t,&edge[i].c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
256 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
7 ms |
384 KB |
Output is correct |
| 8 |
Correct |
14 ms |
640 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 11 |
Correct |
4 ms |
256 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
256 KB |
Output is correct |
| 14 |
Correct |
9 ms |
384 KB |
Output is correct |
| 15 |
Correct |
8 ms |
384 KB |
Output is correct |
| 16 |
Execution timed out |
2078 ms |
1784 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2083 ms |
1732 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2078 ms |
1656 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2085 ms |
1016 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2085 ms |
1036 KB |
Time limit exceeded |
