lightcode's blog

By lightcode, history, 9 years ago, In English

Hello kids,

I am having a bit trouble with this problem from the IOI 1995. I solved part (1) by removing each node and checking for connectivity, but I cannot know how to solve part two, or give some reformulating in terms of graph theory. I cannot really understand what this part B is saying or asking for. (Some simple condition like part (1))

Does anyone have any ideas?

Thanks very much!

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

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From my understanding, you have to report all v such that you can partition all the arrows into two vertex-disjoint* sets P and Q, such that s is in P and t in Q. And P and Q are valid courses according to the 3 properties mentioned in the statement. P is a s - v course and Q is a v - t course.

*: except v, which belongs to both sets.

This task is rather old (1995) and hence the constraints are very low. I couldn't find an online judge for it, but this year's IOI practice task "Graph" was basically task 1 with today's constraints. You can find its statement here: http://ioi2015.kz/content/view/1/270. Check it out.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Part 2, the splitting points, is the same as finding articulation points in an undirected graph. For this part, treat the graph edges as undirected, because we're interested in connectivity between the 2 parts.

There is a lot of information about articulation points on the web, e.g.

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

    I do'd exactly this. For part A, it is similar problems, yes sir, but graph is become directed. But what happen? I got the WA, verdict, for the part B on test 3.

    Can you look it?

    Thank!

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      There is a tricky point: the splitting point can not have outgoing edges to both parts (otherwise these parts share edges).