| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 882895 |
2023-12-04T05:07:15 Z |
Oz121 |
Sirni (COCI17_sirni) |
Java 11 |
|
3924 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[] 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 |
121 ms |
102140 KB |
Output is correct |
| 2 |
Correct |
266 ms |
110632 KB |
Output is correct |
| 3 |
Correct |
133 ms |
109772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
22072 KB |
Output is correct |
| 2 |
Correct |
1053 ms |
106304 KB |
Output is correct |
| 3 |
Correct |
134 ms |
104116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
102596 KB |
Output is correct |
| 2 |
Correct |
110 ms |
102376 KB |
Output is correct |
| 3 |
Correct |
119 ms |
102848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
598 ms |
82444 KB |
Output is correct |
| 2 |
Correct |
1419 ms |
238372 KB |
Output is correct |
| 3 |
Correct |
996 ms |
131480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
427 ms |
47808 KB |
Output is correct |
| 2 |
Runtime error |
2871 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1136 ms |
152868 KB |
Output is correct |
| 2 |
Correct |
2025 ms |
381628 KB |
Output is correct |
| 3 |
Correct |
750 ms |
97880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
642 ms |
55916 KB |
Output is correct |
| 2 |
Correct |
1896 ms |
360456 KB |
Output is correct |
| 3 |
Correct |
925 ms |
108204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1083 ms |
150660 KB |
Output is correct |
| 2 |
Runtime error |
3740 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
739 ms |
151500 KB |
Output is correct |
| 2 |
Runtime error |
3924 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
466 ms |
121220 KB |
Output is correct |
| 2 |
Runtime error |
3464 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
