11857 - Driving Range

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

Moderator: Board moderators

durjay
New poster
Posts: 13
Joined: Tue Oct 06, 2009 5:09 pm
Location: ctg

11857 - Driving Range

Post by durjay » Mon Oct 04, 2010 7:42 am

I think this is simple DFS problem.
I called a dfs then check which road length is maximum
and then give the answer.....
Is my approach is ok?

PLZ give me some critical input output....

Thanx for advance help :D

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11857 - Driving Range

Post by Igor9669 » Mon Oct 04, 2010 8:33 am

Read about MST (minimal spanning tree)!

wazaaaap
New poster
Posts: 7
Joined: Thu Sep 23, 2010 12:55 am

Re: 11857 - Driving Range

Post by wazaaaap » Mon Oct 04, 2010 1:52 pm

I don't know why but I'm not able to understand those graph problems. Do you think i am the problem or problem description is not so good ? And can you give me some guide to improve the ability of understanding the problem.

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11857 - Driving Range

Post by Igor9669 » Mon Oct 04, 2010 2:39 pm

Solve,solve and solve......

vermapratyush
New poster
Posts: 2
Joined: Mon Oct 04, 2010 4:59 pm

Re: 11857 - Driving Range

Post by vermapratyush » Mon Oct 04, 2010 5:13 pm

In my code I have used prims algorithm to find MST. and the edge with maximum length is the output. I am getting TLE..
I submitted my solution without calling the function to find MST (func name is dfs) still i got TLE.. so i think the problem is in variable declaration (for adjacency matrix) very unlikely though.... which i have implemented using array of vectors to make a 2D array..
the input range was 1 million. are there any other alternative of making an adjacency matrix.

Code: Select all


using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
//BEGIN_TEMPLATE_BY_PRATYUSH_VERMA

//CONSTANT
#define INF (1<<31)-1
#define PI 3.1428571428571428571428571428571

//FUNC
#define MAX(i,j) (i)>(j)?(i):(j)
#define MIN(i,j) (i)<(j)?(i):(j)
#define REP(i,a) for((i)=0;(i)<(a);(i)++)
#define REP_(i,a) for((i)=0;(i)<=(a);(i)++)
#define FOR(i,a,b) for((i)=(a);(i)<(b);(i)++)
#define FOR_(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define VAR(V,init) __typeof(init) V=(init)
#define FOREACH(I,C) for(VAR(I,(C).begin());I!=(C).end();I++)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((int)(x.size()))
#define LENGTH(x) ((int)(x.length()))
#define SZ(x) sizeof(x)
#define MEM(m,i) memset((m),(i),SZ(m))
#define PB(x,y) (x).push_back(y)
#define MP(x,y) make_pair(x,y)
#define V(x) vector < x >

typedef pair<int,int>   PII;
typedef pair<char,int>  PCI;
typedef pair<int,PII>   TRI;
typedef V( int )        VI;
typedef V( PII )        VII;
typedef V( TRI )        VTRI;
typedef V( string )     VS;
typedef long long       LL;
typedef long double     LD;

inline string i2s(int number) { stringstream ss; ss << number; return ss.str(); }
inline void input( int &n ) { n=0; int ch=getchar(); while( ch < '0' || ch > '9' ) ch=getchar(); while( ch >= '0' && ch <= '9' ) n = (n<<3)+(n<<1) + ch-'0', ch=getchar(); }
vector<int> adj[1000000];
bool vis[1000000];
int m,n;
//END_TEMPLATE_BY_PRATYUSH_VERMA


struct node {
    int i;
    node (int a) {i=a;}
	   friend bool operator< (const node &a, const node &b)
	   {
			  return (a.i>b.i);
	   		  }

};

int dfs()
{
    int min=0;
    priority_queue<node> s;
    s.push(node (0));
    int i;
    while(!s.empty())
    {
        node t=s.top();
        s.pop();
        vis[t.i]=true;
        REP(i,n)
        {
            if(vis[i]==true || t.i==i) continue;
            if( adj[t.i][i]==-1) continue;
            if(adj[t.i][i]>min) min=adj[t.i][i];
            s.push(node (i));
        }
    }
    REP(i,n)
    if(!vis[i]) return -1;
    return min;
}
int main()
{
    int i,j,k,p,q;
    while(1)
    {
        input(n);
        input(m);
        if(m==0 && n==0) return 0;
        if(m<n-1)
        {
                printf("IMPOSSIBLE\n");
            continue;
        }
        MEM(vis,0);
        REP(i,n) adj[i].clear();
        REP(i,n)
        REP(j,n) PB(adj[i],-1);
        REP(i,m)
        {
            input(p);
            input(q);
            input(k);
//            cin>>p>>q>>k;
            if(adj[p][q]!=-1) k=min(k,min(adj[p][q],adj[q][p]));
            adj[p][q]=k;
            adj[q][p]=k;
        }
        int flag=dfs();
        if(flag==-1) printf("IMPOSSIBLE\n");
        else
        {
        printf("%d\n",flag);
        }
    }
	return 0;
}

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11857 - Driving Range

Post by Igor9669 » Mon Oct 04, 2010 8:13 pm

Yes of course read about Kruskal algorithm!
Here you find a data that needed!

vermapratyush
New poster
Posts: 2
Joined: Mon Oct 04, 2010 4:59 pm

Re: 11857 - Driving Range

Post by vermapratyush » Mon Oct 04, 2010 10:09 pm

ooh.. got it thanks.. :)

durjay
New poster
Posts: 13
Joined: Tue Oct 06, 2009 5:09 pm
Location: ctg

Re: 11857 - Driving Range

Post by durjay » Tue Oct 05, 2010 8:31 pm

Now i got accepted :D

but my runtime is 2.904 :(
I use Kruskal + dfs.
can anyone give me any hints to decrease my runtime....

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11857 - Driving Range

Post by Leonid » Wed Oct 06, 2010 1:14 am

durjay wrote:Now i got accepted :D

but my runtime is 2.904 :(
I use Kruskal + dfs.
can anyone give me any hints to decrease my runtime....
I used Disjoint Sets to solve the problem. My running time is 0.684 sec.

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11857 - Driving Range

Post by Jehad Uddin » Thu Nov 04, 2010 4:39 am

getting wa pls help :roll: :oops:

Code: Select all

got ac code removed :)

Last edited by Jehad Uddin on Thu Nov 04, 2010 7:57 am, edited 1 time in total.

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

Re: 11857 - Driving Range

Post by MRH » Thu Nov 04, 2010 6:01 am

HI In your link funtion return int But you return nothing

hope it help you....

shibly
New poster
Posts: 5
Joined: Wed Sep 22, 2010 7:32 am

Re: 11857 - Driving Range

Post by shibly » Thu Nov 04, 2010 6:07 am

Hafiz in 67th line you used
if(u != v)
but it will be
if(x!=y)

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11857 - Driving Range

Post by Jehad Uddin » Thu Nov 04, 2010 7:58 am

thanks :)

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 11857 - Driving Range

Post by Imti » Tue Jan 04, 2011 6:51 pm

Sorry for Silly Post..I designed a way to solve this problem using DFS.But I dont know which data structure is to use for representing
the Graph.Because size is too much(1 million).I code in c/c++ but array,structure of c/c++ cant support this huge memory.So how to represent graph? :roll: :roll:

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

Re: 11857 - Driving Range

Post by MRH » Thu Jan 06, 2011 3:24 pm

You can use adjacent list or structure ot STL container like as vector

Post Reply

Return to “Volume 118 (11800-11899)”