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
AC × 3
AC × 36
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