| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 882891 |
2023-12-04T04:52:30 Z |
Oz121 |
Sirni (COCI17_sirni) |
Java 11 |
|
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()); }
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
