Submission #1799904
Source Code Expand
import java.util.*; class E implements Comparable<E>{ int x,y; long c; E(int x,int y,long c){ this.x=x;this.y=y;this.c=c; } @Override public int compareTo(E o){ return Long.compare(c,o.c); } } class UnionFind { int[] parent; int[] rank; UnionFind(int n) { this.parent = new int[n]; this.rank = new int[n]; this.clear(); } void clear() { int n = this.parent.length; for (int i = 0; i < n; ++i) { this.parent[i] = i; this.rank[i] = 0; } } void unify(int x, int y) { int rootX = this.root(x); int rootY = this.root(y); if (rootX == rootY) { return; } if (this.rank[rootX] < this.rank[rootY]) { this.parent[rootX] = rootY; } else { this.parent[rootY] = rootX; if (this.rank[rootX] == this.rank[rootY]) { this.rank[rootX]++; } } } int root(int x) { if (this.parent[x] == x) { return x; } return this.parent[x] = this.root(this.parent[x]); } } class Main { static final long I=(1L<<62)-1; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n=Integer.parseInt(scan.next()); int q=Integer.parseInt(scan.next()); List<E>e=new ArrayList<E>(); long[]adj=new long[n]; Arrays.fill(adj,I); for(int i=0;i<q;++i){ int a=Integer.parseInt(scan.next()); int b=Integer.parseInt(scan.next()); long c=Integer.parseInt(scan.next()); e.add(new E(a,b,c)); adj[a]=Math.min(adj[a],c+1); adj[b]=Math.min(adj[b],c+2); } for(int i=0;i<2;++i) for(int j=0;j<n;++j) adj[j]=Math.min(adj[j],adj[(j+n-1)%n]+2); for(int i=0;i<n;++i) e.add(new E(i,(i+1)%n,adj[i])); Collections.sort(e); UnionFind u=new UnionFind(n); long t=0; for(E ee:e){ int x=ee.x; int y=ee.y; long c=ee.c; if(u.root(x)!=u.root(y)){ u.unify(x,y); t+=c; } } System.out.println(t); } }
Submission Info
Submission Time | |
---|---|
Task | G - Zigzag MST |
User | kirika_comp |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1300 |
Code Size | 2229 Byte |
Status | AC |
Exec Time | 1027 ms |
Memory | 102716 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, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 94 ms | 23764 KB |
01-02.txt | AC | 834 ms | 102716 KB |
01-03.txt | AC | 992 ms | 98880 KB |
01-04.txt | AC | 185 ms | 33592 KB |
01-05.txt | AC | 167 ms | 35392 KB |
01-06.txt | AC | 185 ms | 37628 KB |
01-07.txt | AC | 226 ms | 35884 KB |
01-08.txt | AC | 260 ms | 38800 KB |
01-09.txt | AC | 402 ms | 42316 KB |
01-10.txt | AC | 743 ms | 68504 KB |
01-11.txt | AC | 912 ms | 98104 KB |
01-12.txt | AC | 961 ms | 98012 KB |
01-13.txt | AC | 1004 ms | 98828 KB |
01-14.txt | AC | 998 ms | 96512 KB |
01-15.txt | AC | 1014 ms | 99192 KB |
01-16.txt | AC | 1027 ms | 98664 KB |
01-17.txt | AC | 998 ms | 98048 KB |
01-18.txt | AC | 809 ms | 99076 KB |
01-19.txt | AC | 199 ms | 38640 KB |
01-20.txt | AC | 282 ms | 49460 KB |
01-21.txt | AC | 582 ms | 66236 KB |
01-22.txt | AC | 815 ms | 98500 KB |
01-23.txt | AC | 852 ms | 96800 KB |
01-24.txt | AC | 333 ms | 45088 KB |
01-25.txt | AC | 821 ms | 99548 KB |
01-26.txt | AC | 185 ms | 35152 KB |
01-27.txt | AC | 373 ms | 43092 KB |
01-28.txt | AC | 760 ms | 76708 KB |
01-29.txt | AC | 856 ms | 98712 KB |
01-30.txt | AC | 933 ms | 100708 KB |
sample-01.txt | AC | 92 ms | 20820 KB |
sample-02.txt | AC | 94 ms | 23636 KB |
sample-03.txt | AC | 92 ms | 20052 KB |