oj.uz

Submission #882890

# Submission time Handle Problem Language Result Execution time Memory
882890 2023-12-04T04:47:33 Z SansPapyrus683 Sirni (COCI17_sirni) Java 11
84 / 140
 1884 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());
        Set<Integer> unique = new TreeSet<>();
        for (int c = 0; c < cardNum; c++) {
            unique.add(Integer.parseInt(read.readLine()));
        }

        int[] cards = new int[unique.size()];
        int cAt = 0;
        for (int card : unique) {
            cards[cAt++] = card;
        }

        int largest = Arrays.stream(cards).max().getAsInt();
        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 good_mod = nextLargest[at];
                goodLinks[cards[good_mod] % cards[i]].add(new int[]{i, good_mod});
            }
        }

        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 1065 ms 426332 KB Output is correct
2 Correct 1396 ms 632552 KB Output is correct
3 Correct 1123 ms 534604 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 27060 KB Output is correct
2 Runtime error 1417 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 966 ms 422752 KB Output is correct
2 Correct 953 ms 421304 KB Output is correct
3 Correct 986 ms 424264 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 133864 KB Output is correct
2 Correct 1038 ms 223104 KB Output is correct
3 Correct 719 ms 173232 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 86944 KB Output is correct
2 Correct 775 ms 169768 KB Output is correct
3 Correct 500 ms 103128 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 179848 KB Output is correct
2 Correct 1254 ms 334708 KB Output is correct
3 Correct 672 ms 163312 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 50844 KB Output is correct
2 Correct 1285 ms 331988 KB Output is correct
3 Correct 680 ms 165904 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1529 ms 579972 KB Output is correct
2 Runtime error 1577 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 1603 ms 617628 KB Output is correct
2 Runtime error 1565 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 1304 ms 543408 KB Output is correct
2 Runtime error 1884 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -