Submission #882896

#	Time	Username	Problem	Language	Result	Execution time	Memory
882896		Oz121	Sirni (COCI17_sirni)	Java	84 / 140	3919 ms	786432 KiB

sirni

import java.io.*;
import java.util.*;
public class sirni {
    public static int[] parents; public static int[] sizes;
    public static void main(String[] args) {
        Kattio scan = new Kattio();

        int num = scan.nextInt(); int max = -1;
        int[] arr = new int[num];

        for (int i = 0;i<num;i++) {
            arr[i] = scan.nextInt(); max = Math.max(max,arr[i]);
        }
        Arrays.sort(arr);

        ArrayList<Edge> edges = new ArrayList<>();
        for (int i = 0;i<num;i++) {
            int curr = arr[i];
            if (i+1<num) edges.add(new Edge(i,i+1,arr[i+1]%curr));

            int prevIdx = i+1;
            for (int k = curr*2;k<=max;k+=curr) {
                int idx = Arrays.binarySearch(arr,k);
                if (idx<0)
                    idx = (-1)*idx-1;

                if (prevIdx!=idx) edges.add(new Edge(i,idx,arr[idx]%curr));
                prevIdx = idx;
            }
        }

        Edge[] sortedEdges = countingSort(edges,max);
        System.out.println(Kruskal(num, sortedEdges));
    }

    public static long Kruskal(int num, Edge[] edges) { //Number of vertices and queue of edges
        parents = new int[num]; sizes = new int[num];
        for (int i = 0;i<num;i++) parents[i] = i;
        Arrays.fill(sizes,1);

        long cost = 0;

        for (int i = 0;i<edges.length;i++) {
            Edge curr = edges[i];

            if (find(curr.start)!=find(curr.end)) {
                merge(curr.start,curr.end);
                cost += curr.weight;
            }
        }

        return cost;
    }

    public static int find(int x) {
        if (parents[x]!=x)
            parents[x] = find(parents[x]);
        return parents[x];
    }

    public static boolean merge (int a, int b) {
        int pa = find(a); int pb = find(b);
        if (pa==pb)
            return false; //no merge

        if (sizes[pa]<=sizes[pb]) {
            parents[pa] = pb;
            sizes[pb] += sizes[pa];
        } else {
            parents[pb] = pa;
            sizes[pa] += sizes[pb];
        }

        return true;
    }

    public static Edge[] countingSort (ArrayList<Edge> arr, int max) {
        int num = arr.size();

        int[] ps = new int[max+1];
        for (int i = 0;i<num;i++) ps[arr.get(i).weight]++;

        for (int i = 1;i<=max;i++) {
            ps[i] = ps[i-1]+ps[i];
        }

        Edge[] ans = new Edge[num];
        for (int i = num-1;i>=0;i--) {
            ps[arr.get(i).weight]--;
            ans[ps[arr.get(i).weight]] = arr.get(i);
        }
        return ans;
    }

    public static class Edge implements Comparable<Edge> {
        int start; int end; int weight;

        public Edge (int start, int end, int weight) {
            this.start = start; this.end = end; this.weight = weight;
        }

        @Override
        public int compareTo(Edge e) {
            if (this.weight>e.weight) return 1;
            else if (this.weight==e.weight) return 0;
            else return -1;
        }
    }
    static class Kattio extends PrintWriter {
        private BufferedReader r;
        private StringTokenizer st;
        // standard input
        public Kattio() { this(System.in, System.out); }
        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }
        // USACO-style file input
        public Kattio(String problemName) throws IOException {
            super(problemName + ".out");
            r = new BufferedReader(new FileReader(problemName + ".in"));
        }
        // returns null if no more input
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }
        public int nextInt() { return Integer.parseInt(next()); }
        public double nextDouble() { return Double.parseDouble(next()); }
        public long nextLong() { return Long.parseLong(next()); }
    }
}

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