oj.uz

답안 #882891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
882891 2023-12-04T04:52:30 Z Oz121 Sirni (COCI17_sirni) Java 11
70 / 140
 2607 ms 786432 KB 
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));

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

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

        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[] count = new int[max+1];
        for (int i = 0;i<num;i++) count[arr.get(i).weight]++;

        int[] ps = new int[max+1]; ps[0] = count[0];
        for (int i = 1;i<=max;i++) {
            ps[i] = ps[i-1]+count[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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 102688 KB Output is correct
2 Correct 672 ms 216236 KB Output is correct
3 Correct 146 ms 103912 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 24340 KB Output is correct
2 Runtime error 1858 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 106728 KB Output is correct
2 Correct 111 ms 106640 KB Output is correct
3 Correct 123 ms 102596 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 612 ms 84596 KB Output is correct
2 Correct 1665 ms 285116 KB Output is correct
3 Correct 1116 ms 150816 KB Output is correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 405 ms 48068 KB Output is correct
2 Runtime error 2507 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1124 ms 154096 KB Output is correct
2 Correct 2493 ms 494060 KB Output is correct
3 Correct 742 ms 128220 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 634 ms 55348 KB Output is correct
2 Correct 2377 ms 488724 KB Output is correct
3 Correct 1082 ms 155120 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1098 ms 159388 KB Output is correct
2 Runtime error 2607 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 854 ms 178348 KB Output is correct
2 Runtime error 2422 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 473 ms 121488 KB Output is correct
2 Runtime error 2545 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -