Submission #653484

#	Time	Username	Problem	Language	Result	Execution time	Memory
653484		ziduo	timeismoney (balkan11_timeismoney)	Java	95 / 100	1986 ms	16676 KiB

timeismoney

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]);
	    points.add(solve(1,1));
	    set.add(points.get(2)[0]*1000000000L+points.get(2)[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>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;
	}
}

• Subtask 1: 95 / 100