QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#533066 | #8068. Building Roads | theodoregossett | WA | 55ms | 40084kb | Java8 | 3.7kb | 2024-08-25 16:42:24 | 2024-08-25 16:42:24 |
Judging History
answer
import java.util.*;
public class Main {
static class Edge implements Comparable<Edge> {
int vertex;
double weight;
public Edge(int vertex, double weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Double.compare(this.weight, other.weight);
}
}
// Method to compute the Euclidean distance between two points
public static double getDistance(int x1, int y1, int x2, int y2) {
return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
// Prim's algorithm to build MST from a given vertex
public static List<List<Edge>> primMST(int n, int start, int[] xCoordinates, int[] yCoordinates) {
boolean[] visited = new boolean[n];
List<List<Edge>> mst = new ArrayList<>();
for (int i = 0; i < n; i++) {
mst.add(new ArrayList<>());
}
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.add(new Edge(start, 0));
while (!pq.isEmpty()) {
Edge current = pq.poll();
int vertex = current.vertex;
if (visited[vertex]) continue;
visited[vertex] = true;
// For each unvisited adjacent vertex, add to the priority queue
for (int i = 0; i < n; i++) {
if (!visited[i]) {
double distance = getDistance(xCoordinates[vertex], yCoordinates[vertex], xCoordinates[i], yCoordinates[i]);
pq.add(new Edge(i, distance));
mst.get(vertex).add(new Edge(i, distance));
mst.get(i).add(new Edge(vertex, distance));
}
}
}
return mst;
}
// DFS to find the farthest node and its distance from the starting node
public static double[] dfs(List<List<Edge>> mst, int current, boolean[] visited) {
visited[current] = true;
double maxDist = 0;
double secondMaxDist = 0;
for (Edge edge : mst.get(current)) {
if (!visited[edge.vertex]) {
double dist = edge.weight + dfs(mst, edge.vertex, visited)[0];
if (dist > maxDist) {
secondMaxDist = maxDist;
maxDist = dist;
} else if (dist > secondMaxDist) {
secondMaxDist = dist;
}
}
}
return new double[] { maxDist, maxDist + secondMaxDist };
}
// Method to find the diameter of the MST
public static double getTreeDiameter(List<List<Edge>> mst, int start) {
boolean[] visited = new boolean[mst.size()];
double[] result = dfs(mst, start, visited);
return result[1]; // The diameter of the tree is the max of the two longest paths
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] xCoordinates = new int[n];
int[] yCoordinates = new int[n];
for (int i = 0; i < n; i++) {
xCoordinates[i] = scanner.nextInt();
yCoordinates[i] = scanner.nextInt();
}
double minDiameter = Double.MAX_VALUE;
for (int i = 0; i < n; i++) {
// Generate MST from each vertex
List<List<Edge>> mst = primMST(n, i, xCoordinates, yCoordinates);
// Find the diameter of the resulting tree
double diameter = getTreeDiameter(mst, i);
// Track the minimum diameter
minDiameter = Math.min(minDiameter, diameter);
}
System.out.print(minDiameter);
scanner.close();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 55ms
memory: 39300kb
input:
3 0 0 10 0 0 10
output:
20.0
result:
ok found '20.00000', expected '20.00000', error '0.00000'
Test #2:
score: -100
Wrong Answer
time: 51ms
memory: 40084kb
input:
9 0 0 10 0 0 10 -10 0 0 -10 10 10 10 -10 -10 10 -10 -10
output:
114.78708664619074
result:
wrong answer 1st numbers differ - expected: '28.28427', found: '114.78709', error = '3.05834'