Submission #659953

#	Time	Username	Problem	Language	Result	Execution time	Memory
659953		coderInTraining	Sirni (COCI17_sirni)	Java	0 / 140	1894 ms	123488 KiB

sirni

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);
        }

        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;

            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: 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