11631 - Dark roads

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

11631 - Dark roads. WA!!!

Post by sith » Tue Dec 25, 2012 8:42 pm

Hi,

I believe I chose right approach, but I got WA,
Could anybody help with advice or provide some input

Code: Select all

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

class Main {


    public static void main(String[] args) {
   
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));


        try {
            Scanner scanner = new Scanner(reader);

            while (scanner.hasNextInt()) {

                int m = scanner.nextInt();
                int n = scanner.nextInt();

                Distance[] distances = new Distance[n];
                int sum = 0;
                for (int i = 0; i < n; i++) {
                    int from = scanner.nextInt();
                    int to = scanner.nextInt();
                    int distance = scanner.nextInt();
                    distances[i] = new Distance(from, to, distance);
                    sum += distance;
                }

                WeightedQuickUnion quickUnion = new WeightedQuickUnion(m + 1);


                Arrays.sort(distances);

                int totalDistance = 0;

                for (Distance distance : distances) {

                    if (quickUnion.find(distance.from, distance.to)) {
                        continue;
                    }

                    totalDistance += distance.distance;

                    quickUnion.union(distance.from, distance.to);

                }


                writer.write((sum-totalDistance) + "\n");


            }


            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static class Distance implements Comparable<Distance> {
        int from, to, distance;

        Distance(int from, int to, int distance) {
            this.from = from;
            this.to = to;
            this.distance = distance;
        }

        @Override
        public int compareTo(Distance o) {
            int distanceDiff = distance - o.distance;

            if (distanceDiff != 0) {
                return distanceDiff;
            }

            int fromDiff = from - o.from;
            if (fromDiff != 0) {
                return fromDiff;
            }

            return to - o.to;

        }
    }


    static class QuickUnion extends FindUnion {
        public QuickUnion(int n) {
            super(n);
        }

        @Override
        public void union(int p, int q) {
            int i = getRoot(p);
            int j = getRoot(q);
            array[i] = j;
            groups--;
        }

        @Override
        public boolean find(int a, int b) {
            return getRoot(a) == getRoot(b);
        }

        protected int getRoot(int a) {

            if (a == array[a]) {
                return a;
            }
            return getRoot(array[a]);
        }
    }

    static abstract class FindUnion {

        protected final int[] array;
        protected int groups;


        protected FindUnion(int n) {
            this.array = new int[n];
            for (int i = 1; i < array.length; i++) {
                array[i] = i;
            }
            groups = n;
        }


        public abstract void union(int p, int q);

        public abstract boolean find(int p, int q);

        public int getGroups() {
            return groups;
        }
    }


    static class WeightedQuickUnion extends QuickUnion {
        final int[] size;
        public WeightedQuickUnion(int n) {
            super(n);
            size = new int[n];
            for (int i = 0; i < size.length; i++) {
                size[i] = 1;
            }
        }

        @Override
        public void union(int p, int q) {
            int i = getRoot(p);
            int j = getRoot(q);

            if (size[i] < size[j]) {
                array[i] = j;
                size[j] += size[i];
            } else {
                array[j] = i;
                size[i] += size[j];
            }
            groups--;

        }
    }
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11631 - Dark roads. WA!!!

Post by brianfry713 » Wed Dec 26, 2012 11:29 am

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

laituanksa245
New poster
Posts: 20
Joined: Tue Jan 10, 2012 4:23 pm
Location: Vietnam

11631 - Dark roads

Post by laituanksa245 » Sat Dec 29, 2012 12:45 pm

I kept getting TLE on this problem.
Any suggestion to speed up my program ?
I used Kruskal algorithm.

Code: Select all

Code Removed.
Got AC
Last edited by laituanksa245 on Sun Jan 06, 2013 6:12 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11631 - Dark roads TLE

Post by brianfry713 » Sun Dec 30, 2012 9:09 am

Add union find to Kruskal's algorithm.
Check input and AC output for thousands of problems on uDebug!

laituanksa245
New poster
Posts: 20
Joined: Tue Jan 10, 2012 4:23 pm
Location: Vietnam

Re: 11631 - Dark roads TLE

Post by laituanksa245 » Sun Jan 06, 2013 6:12 am

Thanks very much. Got AC :D

Saminur Islam
New poster
Posts: 4
Joined: Tue Dec 10, 2013 10:49 am

Re: 11631 - Dark roads TLE

Post by Saminur Islam » Tue Dec 10, 2013 12:39 pm

I think this is a simple mst problem I use prim algorithm but getting submission error ..... plz help me to find out the problem in my code

Code: Select all

#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<set>
#include<list>
#include<utility>
#include<fstream>
#include<cmath>
using namespace std;

int M,N;
vector<pair<int,int> >node[200001];
bool visited[200001];
int dist[200001];
int parent[200001];
int minkey()
{
    int i,min;
    for(i=0;i<M;i++)
    {
        if(visited[i]==false)
        {
            min=i;
            break;
        }
    }
    for(i=0;i<M;i++)
    {
        if(dist[min]>dist[i] && visited[i]==false) min=i;
    }
    return min;
}

void prim()
{
    int i,j;
    int k,distance;
    int value;
    memset(visited,false,sizeof visited);
    memset(parent,-1,sizeof parent);
    for(int i=0;i<M;i++)dist[i]=1000000;
    dist[0]=0;
    i=0;
    for(i=0;i<M;i++)
    {
        int min= minkey();
        visited[min]=true;
        //cout<<min<<" "<<dist[min]<<endl;
        for(j=0;j<node[min].size();j++)
        {
            pair<int,int>p;
            p=node[min][j];
            value=p.first;
            distance=p.second;
            if(visited[value]==false && distance<dist[value])
            {
                dist[value]=distance;
                parent[value]=min;

            }
        }
    }
}

int main()
{
    //freopen("i.txt","r",stdin);
    int i,j,k;
    int totalcost2;
    int value1,value2,weight;
    while(scanf("%d %d",&M,&N)==2)
    {
        if(M==0&&N==0) break;
        totalcost2=0;
        for(i=0;i<N;i++)
        {
            scanf("%d %d %d",&value1,&value2,&weight);
            totalcost2=totalcost2+weight;
            node[value1].push_back(make_pair(value2,weight));
            node[value2].push_back(make_pair(value1,weight));
        }
        //cout<<totalcost2<<endl;
        prim();
        int totalCost=0;
        for(i=M-1;i>0;i--)
        {
            //cout<<dist[i]<<"\n";
            totalCost+=dist[i];
        }
        //cout<<totalCost<<endl;
        cout<<totalcost2-totalCost<<endl;
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11631 - Dark roads TLE

Post by brianfry713 » Tue Dec 10, 2013 10:06 pm

Your code is now getting wrong answer.
Try input:

Code: Select all

3 2
0 1 2000000
1 2 1
0 0
Output should be 0
Check input and AC output for thousands of problems on uDebug!

Karkat_Vantas
New poster
Posts: 4
Joined: Thu Aug 21, 2014 2:59 am

Re: 11631 - Dark roads

Post by Karkat_Vantas » Sat Nov 15, 2014 7:34 pm

My code returns a compiler error. In my IDE though, it shows no errors, and no warnings except "Unchecked cast from Bag[] to Bag<Main.Edge>[]". The code runs fine on my machine. What are some reasons why the judge would find a different compiling error?

My code also contains different classes (I'm guessing that this is the reason for the error.)
Is

Code: Select all

public class Main{
public static void main(String[] args)
{}
public static class A
{}
public static class B
{}
}
the way to arrange multiple classes in the same file?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11631 - Dark roads

Post by brianfry713 » Mon Nov 17, 2014 11:06 pm

Check My Submissions for your CE.
Check input and AC output for thousands of problems on uDebug!

dreamd_hacker
New poster
Posts: 1
Joined: Mon Jun 08, 2015 11:12 am

Re: 11631 - Dark roads

Post by dreamd_hacker » Mon Jun 08, 2015 11:20 am

Hi, I got TLE three times. Here is my code.

Code: Select all

#include <cstdio>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#define DEBUG 0
using namespace std;

struct edge {
	int f, t, w;
	bool operator <(const edge &other) const {
		return this-> w < other.w; 
	}
};

int find_set(int *s, int v){
	if(s[v] == v)
		return v;
	else
		return find_set(s, s[v]);
}

int main() {
	if (DEBUG)
		freopen("in.txt", "r", stdin);

	int n, m, f, t, w, par1, par2, total, min_sum, select;
	int arr_set[200010];
	while (1) {
		scanf("%d%d", &n, &m);
		if (n == 0 && m == 0)
			break;
		
		total = 0;
		vector<edge> q;
		for(int i = 0; i < m; ++i){
			scanf("%d%d%d", &f, &t, &w);
			edge e = {f, t, w};
			q.push_back(e);
			total += w;
			arr_set[i] = i;
		}
		arr_set[n] = n;
		
		if(n == m + 1){
			printf("0\n");
			continue;
		}
		
		min_sum = 0;
		select = n - 1;
		sort(q.begin(), q.end());
		for(int i = 0; (i < m) && select; ++i){
			edge t = q[i];
			par1 = find_set(arr_set, t.f);
			par2 = find_set(arr_set, t.t);
			if(par1 != par2){
				min_sum += t.w;
				arr_set[par1] = par2;
				select--;
			}
		}
		
		printf("%d\n", total - min_sum);
	}

	return 0;
}


martijnn2008
New poster
Posts: 2
Joined: Sun Aug 31, 2014 5:46 pm

Re: 11631 - Dark roads

Post by martijnn2008 » Fri Nov 13, 2015 8:26 pm

I get a Run Error, can't find out why. Please help.

Code: Select all

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        while(n != 0 && m != 0) {
            solve(n, m, sc);
            n = sc.nextInt();
            m = sc.nextInt();
        }
    }

    static class Edge implements Comparable<Edge> {
        int a, b, w;
        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }

        public int compareTo(Edge e) {
            return this.w - e.w;
        }

        public String toString() {
            return "[(" + a + ", " + b + ") : " + w + "]";
        }
    }

    static void solve(int n, int m, Scanner sc) {
        Edge[] edges = new Edge[m];
        Edge[] tree = new Edge[n - 1];
        int total = 0;
        for (int i = 0; i < m; i++) {
            edges[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
            total += edges[i].w;
        }
        parent = new int[n];
        rank = new int[n];
        int s = 0;
        Arrays.sort(edges);
        for (int i = 0; i < n; i++) { parent[i] = i; }
        for (Edge e : edges) { if (join(e.a, e.b)) { tree[s++] = e; }
        if (s >= n -1) break;} 
        int output = 0;
        for (Edge e : tree) {
            output += e.w;
        }
        System.out.println(total - output);
    }

    static int[] parent;
    static int[] rank;
    static boolean join(int x, int y) {
        /*
        int fx = find(x);
        int fy = find(y);
        if(rank[x] < rank[y])
            parent[x] = fy;
        else {
            parent[y] = fx;
            if (rank[x] != rank[y]) {
                rank[x]++;
            }
        }
        return fx != fy;
        */

        int xrt = find(x);
        int yrt = find(y);
        if (rank[xrt] > rank[yrt]) {
            parent[yrt] = xrt;
        } else {
            parent[xrt] = yrt;
            if (xrt != yrt) {
                rank[xrt]++;
            }
        }
        return xrt != yrt;
    }

    static int find(int x) {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }

}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11631 - Dark roads

Post by brianfry713 » Wed Nov 25, 2015 2:51 am

use class Main
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 116 (11600-11699)”