Submission #653475

# Submission time Handle Problem Language Result Execution time Memory
653475 2022-10-27T01:04:40 Z ziduo timeismoney (balkan11_timeismoney) Java 11
20 / 100
2000 ms 65536 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;
	}
}
# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 25936 KB Time limit exceeded
2 Runtime error 810 ms 65536 KB Execution killed with signal 9
3 Runtime error 1294 ms 65536 KB Execution killed with signal 9
4 Execution timed out 2073 ms 46448 KB Time limit exceeded
5 Execution timed out 2072 ms 21324 KB Time limit exceeded
6 Execution timed out 2053 ms 21176 KB Time limit exceeded
7 Execution timed out 2070 ms 17524 KB Time limit exceeded
8 Execution timed out 2075 ms 15920 KB Time limit exceeded
9 Correct 163 ms 11888 KB Output is correct
10 Correct 161 ms 11860 KB Output is correct
11 Correct 153 ms 11864 KB Output is correct
12 Incorrect 161 ms 11964 KB Output isn't correct
13 Correct 165 ms 11896 KB Output is correct
14 Incorrect 178 ms 12164 KB Output isn't correct
15 Incorrect 181 ms 11868 KB Output isn't correct
16 Incorrect 381 ms 15272 KB Output isn't correct
17 Incorrect 385 ms 15336 KB Output isn't correct
18 Incorrect 374 ms 15448 KB Output isn't correct
19 Incorrect 603 ms 16240 KB Output isn't correct
20 Incorrect 659 ms 15608 KB Output isn't correct