Submission #883187

#	Time	Username	Problem	Language	Result	Execution time	Memory
883187		SansPapyrus683	Sirni (COCI17_sirni)	Java	84 / 140	2057 ms	786432 KiB

sirni

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

public class sirni {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        int cardNum = Integer.parseInt(read.readLine());
        int[] cards = new int[cardNum];
        for (int c = 0; c < cardNum; c++) {
            cards[c] = Integer.parseInt(read.readLine());
        }

        // we can erase the dupes bc modding them with the original one = 0
        cards = Arrays.stream(cards).distinct().sorted().toArray();

        int largest = Arrays.stream(cards).max().getAsInt();
        // nextLargest[i] contains the index of lowest card value that's >= i
        int[] nextLargest = new int[largest + 1];
        Arrays.fill(nextLargest, -1);
        for (int i = 0; i < cards.length; i++) {
            nextLargest[cards[i]] = i;
        }
        for (int c = largest - 1; c >= 0; c--) {
            // if this isn't assigned yet, assign it the previous one
            if (nextLargest[c] == -1) {
                nextLargest[c] = nextLargest[c + 1];
            }
        }

        List<int[]>[] goodLinks = new ArrayList[largest + 1];
        for (int i = 0; i < goodLinks.length; i++) {
            goodLinks[i] = new ArrayList<>();
        }
        for (int i = 0; i < cards.length - 1; i++) {
            // get all relevant cards this card could be connected to
            goodLinks[cards[i + 1] % cards[i]].add(new int[]{i, i + 1});
            for (int at = 2 * cards[i]; at <= largest; at += cards[i]) {
                int goodMod = nextLargest[at];
                goodLinks[cards[goodMod] % cards[i]].add(new int[]{i, goodMod});
            }
        }

        long totalCost = 0;
        DisjointSets linkedCards = new DisjointSets(cards.length);
        for (int c = 0; c <= largest; c++) {
            for (int[] link : goodLinks[c]) {
                if (linkedCards.union(link[0], link[1])) {
                    totalCost += c;
                }
            }
        }

        System.out.println(totalCost);
    }
}

// BeginCodeSnip{DSU (from the module)}
class DisjointSets {
	int[] parents;  // 0-indexed
	int[] sizes;

	public DisjointSets(int size) {
		sizes = new int[size];
		parents = new int[size];
		Arrays.fill(sizes, 1);
		Arrays.fill(parents, -1);
	}

	// finds the "representative" node in a's component
	public int find(int x) {
		return parents[x] == -1 ? x : (parents[x] = find(parents[x]));
	}

	// returns whether the merge changed connectivity
	public boolean union(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);
		if (xRoot == yRoot) { return false; }
		if (sizes[xRoot] < sizes[yRoot]) {
			parents[xRoot] = yRoot;
			sizes[yRoot] += sizes[xRoot];
		} else {
			parents[yRoot] = xRoot;
			sizes[xRoot] += sizes[yRoot];
		}
		return true;
	}

	// returns whether two nodes are in the same connected component
	public boolean connected(int x, int y) { return find(x) == find(y); }
}
// EndCodeSnip

Compilation message (stderr)

Note: sirni.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

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