import java.io.*;
import java.util.*;
public class timeismoney {
static int n;
static int m;
static int[] root;
static ArrayList<int[]> list;
static long[] ans;
static ArrayList<int[]> edges;
public static void main(String[] args)throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
ArrayList<int[]> points = new ArrayList<>();
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
list = new ArrayList<>();
ans = new long[3];
ans[0] = 1000000000000000000L;
edges = new ArrayList<>();
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
list.add(new int[] {Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())});
}
Set<Long> set = new HashSet<>();
points.add(solve(1, 0));
set.add(points.get(0)[0]*1000000000L+points.get(0)[1]);
points.add(solve(0,1));
set.add(points.get(1)[0]*1000000000L+points.get(1)[1]);
for(int i=1; i<points.size(); i++) {
for(int j=0; j<i; j++) {
int v1 = points.get(i)[1]-points.get(j)[1];
int v2 = -(points.get(i)[0]-points.get(j)[0]);
if(v1<0||v2<0) {
v1*=-1;
v2*=-1;
}
if(v1<0||v2<0)continue;
int[] cur = solve(v1, v2);
if((long)cur[0]*v1+(long)cur[1]*v2<(long)points.get(i)[0]*v1+(long)points.get(i)[1]*v2)
if(!set.contains(cur[0]*1000000000L+cur[1])) {
points.add(cur);
set.add(cur[0]*1000000000L+cur[1]);
}
}
}
out.write(ans[1]+" "+ans[2]+"\n");
for(int[] a: edges)out.write(a[0]+" "+a[1]+"\n");
out.flush();
out.close();
}
static int[] solve(int a, int b) {
root = new int[n];
for(int i=0; i<n; i++)root[i]=i;
Collections.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
// TODO Auto-generated method stub
return (o1[2]*a+o1[3]*b)-(o2[2]*a+o2[3]*b);
}
});
LinkedList<Integer> temp = new LinkedList<>();
int t = 0;
int c = 0;
for(int i=0; i<m; i++) {
if(union(list.get(i)[0], list.get(i)[1])) {
temp.add(i);
t+=list.get(i)[2];
c+=list.get(i)[3];
if(temp.size()==n-1)break;
}
}
if((long)t*c<ans[0]) {
ans[0] = (long)t*c;
ans[1]=t;
ans[2]=c;
edges.clear();
for(int num: temp)edges.add(new int[] {list.get(num)[0], list.get(num)[1]});
}
return new int[] {t,c};
}
static boolean union(int a, int b) {
a = find(a);
b = find(b);
if(a==b)return false;
root[b]=a;
return true;
}
static int find(int a) {
if(a!=root[a])return root[a]=find(root[a]);
return a;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
187 ms |
11828 KB |
Output is correct |
| 2 |
Correct |
156 ms |
11824 KB |
Output is correct |
| 3 |
Correct |
155 ms |
11832 KB |
Output is correct |
| 4 |
Correct |
153 ms |
11864 KB |
Output is correct |
| 5 |
Correct |
184 ms |
11816 KB |
Output is correct |
| 6 |
Correct |
180 ms |
11952 KB |
Output is correct |
| 7 |
Correct |
279 ms |
14712 KB |
Output is correct |
| 8 |
Correct |
525 ms |
15288 KB |
Output is correct |
| 9 |
Correct |
154 ms |
11752 KB |
Output is correct |
| 10 |
Correct |
181 ms |
11820 KB |
Output is correct |
| 11 |
Correct |
163 ms |
11628 KB |
Output is correct |
| 12 |
Correct |
211 ms |
13100 KB |
Output is correct |
| 13 |
Correct |
234 ms |
14008 KB |
Output is correct |
| 14 |
Correct |
709 ms |
16168 KB |
Output is correct |
| 15 |
Correct |
637 ms |
16292 KB |
Output is correct |
| 16 |
Execution timed out |
2082 ms |
15272 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2076 ms |
15268 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2086 ms |
15396 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2060 ms |
15848 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2070 ms |
15584 KB |
Time limit exceeded |
