oj.uz

Submission #466963

# Submission time Handle Problem Language Result Execution time Memory
466963 2021-08-21T04:22:22 Z rainliofficial Sirni (COCI17_sirni) Java 11
56 / 140
 5000 ms 786432 KB 
import java.io.*;
import java.util.*;

public class sirni {
    static int n, max = 0, ind = 0;
    static TreeSet<Integer> arr;
    static ArrayList<Edge> edges = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader file = new BufferedReader(new FileReader("file.in"));
        //PrintWriter outfile = new PrintWriter (new BufferedWriter(new FileWriter("Sirni.out")));
        n = Integer.parseInt(file.readLine());
        arr = new TreeSet<>();
        HashMap<Integer, Integer> used = new HashMap<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<n; i++){
            int curr = Integer.parseInt(file.readLine());
            if (!used.containsKey(curr)){
                used.put(curr, 0);
            }
            used.put(curr, used.get(curr)+1);
            if (!map.containsKey(curr)){
                map.put(curr, ind++);
            }
            arr.add(curr);
            max = Math.max(max, curr);
        }
        for (int i : arr){
            findMultiples(i);
        }
        Collections.sort(edges);
        DSU dsu = new DSU(ind+1);
        int ans = 0;
        for (Edge curr : edges){
            if (dsu.find(map.get(curr.from)) != dsu.find(map.get(curr.to))){
                dsu.union(map.get(curr.from), map.get(curr.to));
                ans += curr.cost;
            }
        }
        System.out.println(ans);
    }
    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){
            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];
            }
        }
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 11800 KB Output is correct
2 Correct 1776 ms 150424 KB Output is correct
3 Correct 396 ms 16628 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 11968 KB Output is correct
2 Runtime error 4172 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 245 ms 12108 KB Output is correct
2 Correct 142 ms 9452 KB Output is correct
3 Correct 280 ms 14280 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2419 ms 97044 KB Output is correct
2 Correct 4906 ms 255384 KB Output is correct
3 Correct 2941 ms 139496 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 27752 KB Output is correct
2 Correct 2663 ms 129444 KB Output is correct
3 Correct 2064 ms 89932 KB Output is correct

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3726 ms 151856 KB Output is correct
2 Execution timed out 5054 ms 293176 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1189 ms 42112 KB Output is correct
2 Execution timed out 5057 ms 285368 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3084 ms 120040 KB Output is correct
2 Execution timed out 5083 ms 768428 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3053 ms 141396 KB Output is correct
2 Execution timed out 5082 ms 775420 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 30008 KB Output is correct
2 Execution timed out 5096 ms 525708 KB Time limit exceeded
3 Halted 0 ms 0 KB -