oj.uz

Submission #367971

# Submission time Handle Problem Language Result Execution time Memory
367971 2021-02-19T04:07:00 Z dapig Sirni (COCI17_sirni) Java 11
98 / 140
 5000 ms 786432 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(a)),
						nums.get(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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 50648 KB Output is correct
2 Correct 428 ms 58356 KB Output is correct
3 Correct 262 ms 51296 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 10204 KB Output is correct
2 Correct 667 ms 53956 KB Output is correct
3 Correct 247 ms 51416 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 50628 KB Output is correct
2 Correct 182 ms 50752 KB Output is correct
3 Correct 204 ms 50660 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1487 ms 69596 KB Output is correct
2 Correct 3522 ms 201264 KB Output is correct
3 Correct 1980 ms 88328 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 30808 KB Output is correct
2 Correct 3596 ms 117640 KB Output is correct
3 Correct 1652 ms 82456 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2520 ms 122752 KB Output is correct
2 Correct 4163 ms 232324 KB Output is correct
3 Correct 1564 ms 91632 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1241 ms 40180 KB Output is correct
2 Correct 4861 ms 224192 KB Output is correct
3 Correct 1784 ms 91864 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2524 ms 118280 KB Output is correct
2 Runtime error 4331 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1816 ms 118720 KB Output is correct
2 Execution timed out 5126 ms 762680 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 69364 KB Output is correct
2 Runtime error 4893 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -