oj.uz

Submission #883187

# Submission time Handle Problem Language Result Execution time Memory
883187 2023-12-04T18:15:43 Z SansPapyrus683 Sirni (COCI17_sirni) Java 11
84 / 140
 2057 ms 786432 KB 
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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 984 ms 425552 KB Output is correct
2 Correct 1377 ms 634120 KB Output is correct
3 Correct 1106 ms 534180 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 23212 KB Output is correct
2 Runtime error 1413 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 978 ms 426308 KB Output is correct
2 Correct 945 ms 421256 KB Output is correct
3 Correct 969 ms 422720 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 141608 KB Output is correct
2 Correct 1243 ms 238336 KB Output is correct
3 Correct 948 ms 181808 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 96876 KB Output is correct
2 Correct 970 ms 177576 KB Output is correct
3 Correct 705 ms 109716 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 188012 KB Output is correct
2 Correct 1663 ms 339908 KB Output is correct
3 Correct 876 ms 173804 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 59916 KB Output is correct
2 Correct 1494 ms 332688 KB Output is correct
3 Correct 840 ms 172596 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1681 ms 587932 KB Output is correct
2 Runtime error 1725 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 1722 ms 627624 KB Output is correct
2 Runtime error 1748 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 1491 ms 552192 KB Output is correct
2 Runtime error 2057 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -