Submission #467100

#	Time	Username	Problem	Language	Result	Execution time	Memory
467100		rainliofficial	Sirni (COCI17_sirni)	Java	14 / 140	4236 ms	166632 KiB

sirni

import java.io.*;
import java.util.*;
 
public class sirni {
    static int n, max;
    static TreeSet<Integer> arr;
    static TreeSet<Edge> edges = new TreeSet<>();
    public static void main(String[] args) throws IOException{
        FastIO file = new FastIO();
        //BufferedReader file = new BufferedReader(new FileReader("file.in"));
        //rintWriter outfile = new PrintWriter (new BufferedWriter(new FileWriter("Sirni.out")));
        n = file.nextInt();
        arr = new TreeSet<>();
        for (int i=0; i<n; i++){
            int curr = file.nextInt();
            arr.add(curr);
            max = Math.max(max, curr);
        }
        for (int i : arr){
            findMultiples(i);
        }
        //Collections.sort(edges);
        DSU dsu = new DSU(max+1);
        int ans = 0;
        for (Edge curr : edges){
            if (dsu.find(curr.from) != dsu.find(curr.to)){
                dsu.union(curr.from, curr.to);
                ans += curr.cost;
            }
        }
        file.println(ans);
        file.close();
    }
    public static void findMultiples(int base){
        int k = 1;
        while (base*k <= max){
            if (k == 1){
                if (arr.higher(base*k) != null){
                    int val = arr.higher(base*k);
                    edges.add(new Edge(base, val, val % base)); 
                }
            }else{
                if (arr.ceiling(base*k) != null){
                    int val = arr.ceiling(base*k);
                    edges.add(new Edge(base, val, val % base)); 
                }
            }
            k++;
        }
    }
    static class Edge implements Comparable<Edge>{
        int from, to, cost;
        public Edge(int from ,int to, int cost){
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
        public int compareTo(Edge o){
            if (this.cost == o.cost){
                if (this.to == o.to && this.from == o.from){
                    return 0;
                }else{
                    return this.to - o.to;
                }
            }
            return this.cost - o.cost;
        }
    }
    static class Node implements Comparable<Node>{
        int val;
        int id;
        public Node(int val ,int id){
            this.val = val;
            this.id = id;
        }
        public int compareTo(Node o){
            if (this.val == o.val){
                return this.id - o.id;
            }
            return this.val - o.val;
        }
    }
    static class DSU{
        int n;
        int[] parent;
        int[] size;
        public DSU(int n){
            this.n = n;
            parent = new int[n];
            size = new int[n];
            for (int i=0; i<n; i++){
                parent[i] = i;
                size[i] = 1;
            }
        }
 
        public int find(int a){
            if (parent[a] == a){
                return a;
            }
            return parent[a] = find(parent[a]); // Path compression
        }
 
        public void union(int a, int b){
            a = find(a);
            b = find(b);
            if (a == b){
                // Same component
                return;
            }
            if (size[a] < size[b]){
                // Point a to b
                parent[a] = b;
                size[b] += size[a];
            }else{
                // Point b to a
                parent[b] = a;
                size[a] += size[b];
            }
        }
    }
    static class FastIO extends PrintWriter {
        private InputStream stream;
        private byte[] buf = new byte[1<<16];
        private int curChar, numChars;
    
        // standard input
        public FastIO() { this(System.in,System.out); }
        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }
        // file input
        public FastIO(String i, String o) throws IOException {
            super(new FileWriter(o));
            stream = new FileInputStream(i);
        }
    
        // throws InputMismatchException() if previously detected end of file
        private int nextByte() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars == -1) return -1; // end of file
            }
            return buf[curChar++];
        }
    
        // to read in entire lines, replace c <= ' '
        // with a function that checks whether c is a line break
        public String next() {
            int c; do { c = nextByte(); } while (c <= ' ');
            StringBuilder res = new StringBuilder();
            do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
            return res.toString();
        }
        public int nextInt() { // nextLong() would be implemented similarly
            int c; do { c = nextByte(); } while (c <= ' ');
            int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = 10*res+c-'0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }
        public double nextDouble() { return Double.parseDouble(next()); }
    }
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 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