Submission #1051720
Source Code Expand
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int Q = sc.nextInt(); int[] A = new int[Q]; int[] B = new int[Q]; long[] C = new long[Q]; long[] min_cost = new long[N]; Arrays.fill(min_cost, Long.MAX_VALUE/ 10); PriorityQueue<Edge> pq = new PriorityQueue<>(); for (int i = 0; i < Q; ++i) { A[i] = sc.nextInt(); B[i] = sc.nextInt(); C[i] = sc.nextInt(); pq.add(new Edge(A[i], B[i], C[i])); min_cost[A[i]] = Math.min(min_cost[A[i]], C[i] + 1); min_cost[B[i]] = Math.min(min_cost[B[i]], C[i] + 2); } for (int i = 0; i < 2 * N; ++i) { min_cost[(i + 1) % N] = Math.min(min_cost[(i + 1) % N], min_cost[i % N] + 2); } for (int i = 0; i < N; ++i) { pq.add(new Edge(i, (i + 1) % N, min_cost[i])); } DJSet ds = new DJSet(N); long ret = 0; while (!pq.isEmpty()) { Edge edge = pq.poll(); if (ds.equiv(edge.a, edge.b)) continue; ret += edge.cost; ds.setUnion(edge.a, edge.b); pq.add(new Edge(edge.b, (edge.a + 1) % N, edge.cost + 1)); } System.out.println(ret); } static class DJSet { int n = 1; int[] upper; public DJSet(int n) { this.n = n; upper = new int[n]; Arrays.fill(upper, -1); } int root(int x) { return upper[x] < 0 ? x : (upper[x] = root(upper[x])); } boolean equiv(int x, int y) { return root(x) == root(y); } void setUnion(int x, int y) { x = root(x); y = root(y); if (x != y) { if (upper[x] < upper[y]) { int d = x; x = y; y = d; } upper[y] += upper[x]; upper[x] = y; } } } static class Edge implements Comparable<Edge> { int a; int b; long cost; public Edge(int a, int b, long cost) { this.a = a; this.b = b; this.cost = cost; } @Override public int compareTo(Edge o) { return Long.compare(this.cost, o.cost); } } }
Submission Info
Submission Time | |
---|---|
Task | G - Zigzag MST |
User | fortoobye |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1300 |
Code Size | 2007 Byte |
Status | AC |
Exec Time | 1309 ms |
Memory | 152028 KB |
Judge Result
Set Name | sample | all | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1300 / 1300 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt |
all | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 130 ms | 9808 KB |
01-02.txt | AC | 1036 ms | 149436 KB |
01-03.txt | AC | 1248 ms | 151288 KB |
01-04.txt | AC | 354 ms | 32564 KB |
01-05.txt | AC | 382 ms | 32496 KB |
01-06.txt | AC | 368 ms | 32432 KB |
01-07.txt | AC | 372 ms | 32692 KB |
01-08.txt | AC | 376 ms | 34812 KB |
01-09.txt | AC | 568 ms | 36964 KB |
01-10.txt | AC | 926 ms | 88028 KB |
01-11.txt | AC | 1180 ms | 151032 KB |
01-12.txt | AC | 1308 ms | 151144 KB |
01-13.txt | AC | 1294 ms | 151584 KB |
01-14.txt | AC | 1304 ms | 151308 KB |
01-15.txt | AC | 1265 ms | 151756 KB |
01-16.txt | AC | 1284 ms | 151720 KB |
01-17.txt | AC | 1276 ms | 152028 KB |
01-18.txt | AC | 1216 ms | 152020 KB |
01-19.txt | AC | 337 ms | 32292 KB |
01-20.txt | AC | 422 ms | 36184 KB |
01-21.txt | AC | 846 ms | 66124 KB |
01-22.txt | AC | 1176 ms | 149956 KB |
01-23.txt | AC | 1171 ms | 151620 KB |
01-24.txt | AC | 593 ms | 34732 KB |
01-25.txt | AC | 1309 ms | 151464 KB |
01-26.txt | AC | 362 ms | 33576 KB |
01-27.txt | AC | 636 ms | 39508 KB |
01-28.txt | AC | 1077 ms | 89312 KB |
01-29.txt | AC | 1220 ms | 151556 KB |
01-30.txt | AC | 1271 ms | 151268 KB |
sample-01.txt | AC | 129 ms | 9680 KB |
sample-02.txt | AC | 138 ms | 9800 KB |
sample-03.txt | AC | 129 ms | 9804 KB |