| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 653467 | ziduo | timeismoney (balkan11_timeismoney) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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;
}
}