what's is the wrong with this solution ?: i find the shortest path from the first vertx in the chain to the last ( with bfs) an print that path.i read my code , and I think it's correct ,say if I misunderstood the problem

You have.

I can not understand any thing else that I said , I read the problem description many times !!
    *  the initial and final vertices of the chains p and q coincide;
    * the edges in the chain q are in the same order as in the chain p;
    * the chain q has the minimal possible number of edges under the given conditions.

means that , it should be a path from first vertex to last ,and should use only the chains edges and should be minimal . so is the shortest path between first and last!!
could you pleas give me a test, that my algorithm crashs?

Yes after the contest is finished ;-)

thnx! ;-)

the edges in the chain q are in the same order as in the chain p;

BFS breaks this rule

Can you share tests now? I also want to know, what was in the 7th test:)

something like that

13
1 2 3 4 5 6 7 6 2 6 8 9 7

my answer is 1 2 6 7,I think it's right,but still Wa test 7

try this test
17
1 2 3 4 5 6 7 2 8 9 5 10 8 9 11 3 9

1 2 6 7 - is not correct answer check yourself
1 2 6 8 9 7 - correct

to Piratek-(akaDK) : Please said me why 1 2 8 9 is not correct? thx

My program says
1 2 8 9
for
17
1 2 3 4 5 6 7 2 8 9 5 10 8 9 11 3 9

and
1 2 6 8 9 7
for
13
1 2 3 4 5 6 7 6 2 6 8 9 7

both answers seem correct, but i'm still getting WA7. What is the problem with it?

This test helped me to pass 7
13
1 2 3 4 5 6 7 3 6 11 12 10 7
(1 2 3 4 5 6 7)
However, I got WA 12 :-(

Then I invented this one
15
1 2 3 12 4 5 6 7 3 6 11 12 10 7 6
(1 2 3 6)
And finally got AC..

13
1 2 3 4 5 6 7 6 2 6 8 9 7

Why not (1 2 6 7) ??

For input
13
1 2 3 4 5 6 7 6 2 6 8 9 7

the output
1 2 6 7
is wrong, because here edge (6,7) comes after (2,6),
but in input edge (6,7) comes before edge (2,6).

Hint: Don't use BFS, there is a simple O(n) solution,
you don't need to construct graph.

thanks

But if decided to use BFS?
It is important to know:
1. Can vertex be used multiply in BFS search- Yes.
2.Can edge be used multiply in BFS search-Yes.
Thus what objects should we use  in BFS constructing
and how avoid loop in BFS.
Good mastering in BFS more important than
cleverness by the chance.
P.S.
Ac with BFS. 18 bad submissions on test 3 were answer: v1-
I think that it is stupid trick. Case v1=v2 should
be processed as common.
BFS:
1)used pair(r1,r2) adjacent edges and r2 after r1 as
object of layers of BFS because this pair can be meet in
searching uniquely. And must use set<pair> to defining
that pair is new.
2) used vector<int> sloi1,sloi2 for layers of BFS
and struct pair data[1000000] as store of all items of BFS.
Time Ac is bad but approach is in standard layout.
After first Ac I had got Tle 17 because of new redjudjement.
Wanted to have Ac throught BFS and no DP.
I recoded BFS radically:
1) foud all states on reading data stage and stored its in
array data[3000000]
2) used char met[3000000] to control uniquness of new states on searchind in BFS
These helped to take AC 0.640c.







Edited by author 08.11.2008 12:55

Infinity, i've produced correct answer to your test, but  WA12 anyway :(

give more tests, please

I think you have just a bug somewhere.. Because I had. If you've passed 7, the idea seems to be right.. Try to check your code better.. I don't have more good tests