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));
long t = System.currentTimeMillis();
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((long)cur[0]*1000000000L+cur[1])) {
points.add(cur);
set.add(cur[0]*1000000000L+cur[1]);
}
}
if(System.currentTimeMillis()-t>1500)break;
}
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 |
220 ms |
11828 KB |
Output is correct |
| 2 |
Correct |
186 ms |
11708 KB |
Output is correct |
| 3 |
Correct |
161 ms |
11640 KB |
Output is correct |
| 4 |
Correct |
209 ms |
11648 KB |
Output is correct |
| 5 |
Correct |
194 ms |
11716 KB |
Output is correct |
| 6 |
Correct |
207 ms |
11672 KB |
Output is correct |
| 7 |
Correct |
357 ms |
14548 KB |
Output is correct |
| 8 |
Correct |
605 ms |
15216 KB |
Output is correct |
| 9 |
Correct |
185 ms |
11700 KB |
Output is correct |
| 10 |
Correct |
206 ms |
11500 KB |
Output is correct |
| 11 |
Correct |
198 ms |
11696 KB |
Output is correct |
| 12 |
Correct |
231 ms |
13092 KB |
Output is correct |
| 13 |
Correct |
280 ms |
14044 KB |
Output is correct |
| 14 |
Correct |
785 ms |
15900 KB |
Output is correct |
| 15 |
Correct |
615 ms |
16176 KB |
Output is correct |
| 16 |
Correct |
1662 ms |
16136 KB |
Output is correct |
| 17 |
Correct |
1649 ms |
15976 KB |
Output is correct |
| 18 |
Correct |
1646 ms |
16328 KB |
Output is correct |
| 19 |
Correct |
1660 ms |
16320 KB |
Output is correct |
| 20 |
Incorrect |
1653 ms |
16684 KB |
Output isn't correct |
