oj.uz

Submission #659955

# Submission time Handle Problem Language Result Execution time Memory
659955 2022-11-20T03:23:26 Z coderInTraining Sirni (COCI17_sirni) Java 11
84 / 140
 3226 ms 786432 KB 
import java.util.*;

public class sirni {

    public static int disjoint[]; 
	public static int size[];
	public static int find(int v) {
		if (disjoint[v] == -1) {
			return v;
		}
		disjoint[v] = find(disjoint[v]);
		return disjoint[v];
	}

	public static void union(int u, int v) {
		int uroot = find(u);
		int vroot = find(v);
		if (uroot == vroot) {
			return;
		}
		if (size[uroot] < size[vroot]) {
			disjoint[uroot] = vroot;
            size[vroot] += size[uroot];
		} else {
			disjoint[vroot] = uroot;
            size[uroot] += size[vroot];
		}
	}
    public static void main (String[]args) {
        Scanner scan = new Scanner (System.in);

        int length = scan.nextInt();

        ArrayList<Integer> values = new ArrayList<Integer>();
        HashSet <Integer> seen = new HashSet <Integer>();

        int max = 0;

        for (int i = 0; i < length; i++) {
            int cur = scan.nextInt();

            if (seen.contains(cur)) {
                continue;
            }

            seen.add(cur);
            values.add(cur);

            max = Math.max(max, cur);
        }

        Collections.sort(values);

        int [] next = new int [max + 1];
        Arrays.fill(next, -1);

        for (int i = 0; i < values.size(); i++) {
            int value = values.get(i);

            next[value] = i;
        }

        for (int i = max; i >= 1; i--) {
            if (next[i] != -1) {
                continue;
            }

            next[i] = next[i + 1];
        }

        ArrayList<Triplet> edges = new ArrayList<Triplet>();

        for (int i = 0; i < values.size(); i++) {
            int value = values.get(i);
            int newValue = value;

            if (i + 1 < values.size()) {
                Triplet addingTriplet = new Triplet (i, i + 1, values.get(i + 1) % values.get(i));
                edges.add(addingTriplet);
            }

            for (int j = 2; j <= max; j++) {
                if (j * value > max) {
                    break;
                }

                newValue = value * j;
                int index = next[newValue];

                int firstIndex = i;
                int secondIndex = index;
                int cost = values.get(index) % value;

                Triplet addingTriplet = new Triplet (firstIndex, secondIndex, cost);
                edges.add(addingTriplet);
            }
        }

        Collections.sort(edges);

        disjoint = new int [values.size()];
        size = new int [values.size()];
        
        Arrays.fill(disjoint, -1);
        Arrays.fill(size, 1);

        long cost = 0;

        for (int i = 0; i < edges.size(); i++) {
            int firstNode = edges.get(i).firstNode;
            int secondNode = edges.get(i).secondNode;
            int edgeCost = edges.get(i).edgeCost;

            if (find(firstNode) != find(secondNode) || find(firstNode) == -1 || find(secondNode) == -1) {
                union(firstNode, secondNode);
                cost += edgeCost;
            }
        }

        System.out.println(cost);
    }

    private static class Triplet implements Comparable<Triplet> {
        int firstNode;
        int secondNode;
        int edgeCost;

        public Triplet (int firstNode, int secondNode, int edgeCost) {
            this.firstNode = firstNode;
            this.secondNode = secondNode;
            this.edgeCost = edgeCost;
        }

        public int compareTo (Triplet t) {
            return (edgeCost - t.edgeCost);
        }
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 54644 KB Output is correct
2 Correct 1182 ms 204608 KB Output is correct
3 Correct 442 ms 55080 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 54780 KB Output is correct
2 Correct 278 ms 52300 KB Output is correct
3 Correct 402 ms 55164 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1547 ms 70800 KB Output is correct
2 Correct 2556 ms 199940 KB Output is correct
3 Correct 1788 ms 103568 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 983 ms 29640 KB Output is correct
2 Correct 2133 ms 122100 KB Output is correct
3 Correct 1504 ms 67676 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2001 ms 125456 KB Output is correct
2 Correct 3226 ms 261612 KB Output is correct
3 Correct 1778 ms 101268 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1069 ms 36816 KB Output is correct
2 Correct 3122 ms 260496 KB Output is correct
3 Correct 1746 ms 104732 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1826 ms 123248 KB Output is correct
2 Runtime error 2885 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 1792 ms 155112 KB Output is correct
2 Runtime error 2843 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

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