10859 Placing Lampposts

[crip121]

after very little effort i came up with a dp solution which has been rejected (WA). but my problem is that, i think judge contains isolated vertex ( junction ). can anybody help me, what will be our choice if there is an isolated vertex? should we place i lamp there or will skip it as there is no road to lightning up

anyway, any ac code's output is wellcome

Code: Select all

11
4 3
0 1
1 2
2 3
6 5
0 1
0 2
0 3
0 4
4 5

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


and my wa output

Code: Select all

2 1 2
2 1 4
4 0 8
4 1 6
3 2 3
3 1 5
3 0 7
3 0 6
4 2 5
4 1 7
1 0 1


though i think my output is right except the last one. really confused about it

[sohel]

Yes, you have to make sure all the roads receive lights. So, there is no need to place lampposts on isolated nodes!

[crip121]

thx vaia, got ac already, in ranklist 5-th
nice problem

output from my previous post is correct.