mbaros's blog

Need help for problem 320B
By mbaros, 11 years ago, In English

I am trying to solve the problem 320B - Пинг-Понг (упрощенная версия) with BFS, but getting wrong answer. The idea is as follows: If we add a pair (a,b) to our set, then I check the ways with remaining pairs in my massive "mark". So if we can move from pair x to y than mark[x][y]=1. Otherwise it equals 0.

In case of checking way form x to y I am using BFS. I starting to seek from peak x until y will be found. Otherwise I print No.

Please someone help me to find the mistake in my 3956387 solution.

Thanks.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

Here I leave my solution is a bfs too.

define MAXN 200

using namespace std;

struct inter{ int x, y, id; inter(int x1=0, int y1=0, int id1=0){ x = x1; y = y1; id = id1; } bool operator < ( const inter & r )const{ if ( x != r.x )return x<r.x; return y<r.y; } };

inter ar[MAXN]; int q, a, b, p, c=1;

bool bfs(int ini, int fin){ bool mark[c+1]; memset(mark,0,sizeof(mark)); mark[ini] = true; queue Q; Q.push( ar[ini] ); while ( !Q.empty() ){ int r, t, i; r = Q.front().x; t = Q.front().y; i = Q.front().id; Q.pop(); for ( int i=1; i<c; i++){ if ( !mark[i] && ( (ar[i].x < r && r<ar[i].y) || (ar[i].x < t && t<ar[i].y) ) ){ mark[i] = true; if ( ar[i].id==fin )return true; Q.push(ar[i]); } } } return false; }

int main() {

scanf("%d", &q);
for ( int i=0; i<q; i++ ){
    scanf("%d%d%d", &p, &a, &b);
    if ( p==1 ){
        ar[c] = inter(a,b,c);
        c++;
    }
    else{
        if ( bfs(a,b) )cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}
return 0;

}

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The error is in the line where you wrote flag[1]=1, where actually you should have wrote flag[x]=1. I changed that and got accepted.

Anyway, making a queue with standard arrays and variables to store the size is much harder to code and I do not recommend it in contests. You have the STL library that does all the work for you, all you have to do is write Queue.push(x) to add an element and Queue.front(), Queue.pop() to get the next one and remove it. Get used to the STL libraries, they will make your life much easier :)

And another thing, DFS is much simpler to code than BFS, and it works just as fast (if not faster) in problems where the question is "Is there a path from A to B?". If the problem was asking you the shortest distance from A to B, then BFS would be the ideal choice, but it's only asking you if there's a way to go from A to B, so do DFS.

Here is a readable submission I just coded. Take a look for reference if you like 3956944

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oooooo. That was an impermissible and careless mistake, which i didn't see 2 hours. Thank You very much diego_v1

    → Reply