답안 #653480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653480 2022-10-27T01:12:18 Z ziduo 시간이 돈 (balkan11_timeismoney) Java 11
75 / 100
2000 ms 16292 KB
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;
	}
}
# 결과 실행 시간 메모리 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