oj.uz

Submission #367968

# Submission time Handle Problem Language Result Execution time Memory
367968 2021-02-19T04:04:28 Z dapig Sirni (COCI17_sirni) Java 11
0 / 140
 3465 ms 123468 KB 
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 51008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 10332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 228 ms 50720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1661 ms 69864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 737 ms 30728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3465 ms 123468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1271 ms 40444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2452 ms 118968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1812 ms 118284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 894 ms 69144 KB Output isn't correct
2 Halted 0 ms 0 KB -