11857 - Driving Range

Moderator: Board moderators

11857 - Driving Range

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

PLZ give me some critical input output....

durjay
New poster

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

Re: 11857 - Driving Range

Igor9669
Learning poster

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

Re: 11857 - Driving Range

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.
wazaaaap
New poster

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

Re: 11857 - Driving Range

Solve,solve and solve......
Igor9669
Learning poster

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

Re: 11857 - Driving Range

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_VERMAstruct 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;}`
vermapratyush
New poster

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

Re: 11857 - Driving Range

Here you find a data that needed!
Igor9669
Learning poster

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

Re: 11857 - Driving Range

ooh.. got it thanks..
vermapratyush
New poster

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

Re: 11857 - Driving Range

Now i got accepted

but my runtime is 2.904
I use Kruskal + dfs.
can anyone give me any hints to decrease my runtime....
durjay
New poster

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

Re: 11857 - Driving Range

durjay wrote:Now i got accepted

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.
Leonid
Experienced poster

Posts: 148
Joined: Thu Dec 22, 2005 5:50 pm

Re: 11857 - Driving Range

getting wa pls help
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.
Learning poster

Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11857 - Driving Range

MRH
Learning poster

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

Re: 11857 - Driving Range

Hafiz in 67th line you used
if(u != v)

but it will be
if(x!=y)
shibly
New poster

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

Re: 11857 - Driving Range

thanks
Learning poster

Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11857 - Driving Range

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?
Imti
Learning poster

Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm

Re: 11857 - Driving Range

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

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

Next