Hi everyone , i'm trying to solve SPOJ POLQUERY from COCI 2006 (Croatian Olympiad in Informatics) but i don't understand oficial solutions. Can somebody explain me ideas in order to solve this challenger problem.

Thanks in Advance.

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3655 |

4 | ksun48 | 3547 |

5 | jiangly | 3492 |

6 | Miracle03 | 3480 |

7 | ecnerwala | 3400 |

8 | maroonrk | 3385 |

9 | peehs_moorhsum | 3384 |

10 | sunset | 3338 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 215 |

2 | YouKn0wWho | 190 |

2 | Um_nik | 190 |

4 | sus | 183 |

5 | awoo | 182 |

6 | Errichto | 179 |

7 | tourist | 177 |

8 | -is-this-fft- | 173 |

9 | Radewoosh | 170 |

10 | Ashishgup | 169 |

Hi everyone , i'm trying to solve SPOJ POLQUERY from COCI 2006 (Croatian Olympiad in Informatics) but i don't understand oficial solutions. Can somebody explain me ideas in order to solve this challenger problem.

Thanks in Advance.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/29/2021 01:51:12 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

If a road connecting G1 and G2 disconnects two vertices A and B, that means the number of connected components has increased. By definition, this means the road is a bridge.

What may not be obvious is the inverse: if G1-G2 is a bridge, this means that if

anypath from A to B goes through G1-G2, thenallpaths from A to B use the G1-G2 road. In other words, a necessary and sufficient condition for the path to be blocked is that G1-G2 is a bridge and is used in at least one path from A-B. So the algorithm is simply:It's still not clear how to find the paths. The trick is to consider only a spanning tree of the graph (the DFS tree, for example). In that case there is only a single path between any pair of vertices, and it's easy to check if G1-G2 belongs to it.

Query 2 is very similar.

Very nice idea and explanation , i don't really know that property about bridges.

Thanks.

How was "very similar" did you mean?

ffao I could not develop a similar claim for articulation vertices in query2. Could you please explain it in some detail ?

I am very weak in this area so I may be wrong. Please feel free to point out any mistakes.

For articulation vertices, they split the graph into biconnected components. If you create a graph of biconnected components as well as articulation vertices, it will look like a tree. Then you can find out, first if the deleted node is an articulation vertex, AND if path from bi-component of A to bi-component of B in this tree passes through the deleted node. If both are true then A is disconnected from B.

L.

can anyone tell me that after query of type 1 do we keep the baracades on the road that we didn't use and also if we remove c does this mean that c is removed permanenetly or just for that query it is not considered. I'm confused and i don't want to see the solution or read anything about the solution .So if you could just answer my query. Thanks in advance.

I am using the idea that you told but I get WA on 10th test case.

Where did you find official solutions, mate?? pl. share the link

Here is an easy to understand and short solution :- Link on Github

My point of confusion. In Line 61:

if(desc(a, v) == desc(b, v)) puts("da");why just desc of v ; a,b can be ancestor of u as well.