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));
points.add(solve(0,1));
points.add(solve(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(set.contains(v1*1000000000L+v2))continue;
if(v1<0||v2<0) {
v1*=-1;
v2*=-1;
}
if(v1<0||v2<0)continue;
set.add(v1*1000000000L+v2);
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)
points.add(cur);
}
if(System.currentTimeMillis()-t>1825)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 |
172 ms |
11824 KB |
Output is correct |
| 2 |
Correct |
149 ms |
11660 KB |
Output is correct |
| 3 |
Correct |
155 ms |
11804 KB |
Output is correct |
| 4 |
Correct |
165 ms |
11840 KB |
Output is correct |
| 5 |
Correct |
173 ms |
11868 KB |
Output is correct |
| 6 |
Correct |
177 ms |
11896 KB |
Output is correct |
| 7 |
Correct |
282 ms |
14680 KB |
Output is correct |
| 8 |
Correct |
480 ms |
15376 KB |
Output is correct |
| 9 |
Correct |
152 ms |
11824 KB |
Output is correct |
| 10 |
Correct |
1940 ms |
35236 KB |
Output is correct |
| 11 |
Correct |
264 ms |
14912 KB |
Output is correct |
| 12 |
Correct |
1928 ms |
29096 KB |
Output is correct |
| 13 |
Correct |
1942 ms |
29388 KB |
Output is correct |
| 14 |
Correct |
1961 ms |
18680 KB |
Output is correct |
| 15 |
Correct |
1956 ms |
18828 KB |
Output is correct |
| 16 |
Correct |
1955 ms |
16944 KB |
Output is correct |
| 17 |
Correct |
1954 ms |
16968 KB |
Output is correct |
| 18 |
Correct |
1994 ms |
16796 KB |
Output is correct |
| 19 |
Correct |
1961 ms |
16692 KB |
Output is correct |
| 20 |
Incorrect |
1968 ms |
16612 KB |
Output isn't correct |
