oj.uz

답안 #882896

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
882896 2023-12-04T05:09:06 Z Oz121 Sirni (COCI17_sirni) Java 11
84 / 140
 3919 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));

            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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 67420 KB Output is correct
2 Correct 237 ms 71764 KB Output is correct
3 Correct 119 ms 64888 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 22208 KB Output is correct
2 Correct 1037 ms 70488 KB Output is correct
3 Correct 122 ms 64628 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 63340 KB Output is correct
2 Correct 97 ms 63424 KB Output is correct
3 Correct 108 ms 63416 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 589 ms 82240 KB Output is correct
2 Correct 1389 ms 244200 KB Output is correct
3 Correct 1008 ms 125148 KB Output is correct

Subtask #5
0 / 14.0

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

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1088 ms 148940 KB Output is correct
2 Correct 2005 ms 381672 KB Output is correct
3 Correct 734 ms 97856 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 653 ms 50336 KB Output is correct
2 Correct 1991 ms 352440 KB Output is correct
3 Correct 966 ms 100144 KB Output is correct

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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