답안 #653474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653474 2022-10-27T01:03:51 Z ziduo 시간이 돈 (balkan11_timeismoney) Java 11
60 / 100
652 ms 16340 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]);
	    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(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 170 ms 11824 KB Output is correct
2 Correct 151 ms 11884 KB Output is correct
3 Correct 153 ms 11928 KB Output is correct
4 Correct 154 ms 11732 KB Output is correct
5 Correct 169 ms 11776 KB Output is correct
6 Correct 166 ms 11980 KB Output is correct
7 Correct 266 ms 14672 KB Output is correct
8 Correct 473 ms 15408 KB Output is correct
9 Correct 148 ms 11832 KB Output is correct
10 Correct 148 ms 11908 KB Output is correct
11 Correct 160 ms 11824 KB Output is correct
12 Incorrect 165 ms 11872 KB Output isn't correct
13 Correct 157 ms 11864 KB Output is correct
14 Incorrect 176 ms 12068 KB Output isn't correct
15 Incorrect 170 ms 11992 KB Output isn't correct
16 Incorrect 365 ms 15256 KB Output isn't correct
17 Incorrect 368 ms 15424 KB Output isn't correct
18 Incorrect 369 ms 15172 KB Output isn't correct
19 Incorrect 572 ms 16340 KB Output isn't correct
20 Incorrect 652 ms 15748 KB Output isn't correct