Submission #367968

#	Time	Username	Problem	Language	Result	Execution time	Memory
367968		dapig	Sirni (COCI17_sirni)	Java	0 / 140	3465 ms	123468 KiB

sirni

import java.io.*;
import java.util.*;

class sirni {

	public static void main(String[] args) throws IOException {

		sirni obj = new sirni();

		obj.doStuff();

	}
	
	class SortArr implements Comparator<int[]> {

		@Override
		public int compare(int[] o1, int[] o2) {
			return o1[2]-o2[2];
		}
		
	}
	
	int[] gen(int a, int b) {
		return new int[]
				{a, next[b],
				Math.min((nums.get(next[b])%nums.get(next[a])),
						nums.get(next[a])%nums.get(next[b]))};
	}
	
	int[] par, rank;
	int f(int n) {
		if (par[n] != n) par[n] = f(par[n]);
		return par[n];
	}
	boolean u(int a, int b) {
		a = f(a); b = f(b);
		if (a==b) return false;
		if (rank[b] > rank[a]) {
			int temp = b;
			b = a;
			a = temp;
		}
		rank[a] += rank[b];
		par[b] = a;
		return true;
	}
	
	long kruskal() {
		par = new int[nums.size()];
		rank = new int[nums.size()];
		for (int i = 0; i < par.length; i++) {
			par[i] = i; rank[i] = 1;
		}
		
		long ans = 0;
		while (!pq.isEmpty()) {
			int[] next = pq.poll();
			if (u(next[0], next[1])) ans += next[2];
		}
		return ans;
	}
	
	int[] numsold;
	ArrayList<Integer> nums = new ArrayList<>(100000);
	int[] next;
	PriorityQueue<int[]> pq = new PriorityQueue<>(new SortArr());
	private void doStuff() throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		numsold = new int[Integer.parseInt(br.readLine())];
		for (int i = 0; i < numsold.length; i++) {
			numsold[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		
		Arrays.sort(numsold);
		nums.add(numsold[0]);
		for (int i = 1; i < numsold.length; i++) {
			if (nums.get(nums.size()-1) != numsold[i])
				nums.add(numsold[i]);
		}
		next = new int[nums.get(nums.size()-1)+1];
		int lastpos = 0;
		for (int i = 0; i < next.length; i++) {
			next[i] = lastpos;
			if (nums.get(lastpos) == i) lastpos++;
		}
		
		for (int i = 0; i < nums.size()-1; i++) {
			int inc = nums.get(i);
			pq.add(gen(i, inc+1));
			int lastval = next[inc+1];
			int cur = inc+inc;
			while (cur < next.length) {
				if (next[cur] != lastval) {
					pq.add(gen(i, cur));
					lastval = next[cur];
				}
				cur += inc;
			}
		}
		
		System.out.println(kruskal());

	}

}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14