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