I recently spotted this problem of IOI 2018. I couldn't come up with a proper approach. Only thing that I know is the solution is associated with graph. Can you please help me to solve this problem?

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

1 | tourist | 3372 |

2 | mnbvmar | 3345 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | Radewoosh | 3230 |

5 | scott_wu | 3189 |

6 | Benq | 3187 |

7 | LHiC | 3171 |

8 | Um_nik | 3155 |

9 | V--o_o--V | 3152 |

10 | Petr | 3139 |

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

1 | Radewoosh | 191 |

2 | Errichto | 172 |

3 | rng_58 | 159 |

4 | neal | 156 |

5 | Um_nik | 154 |

5 | tourist | 154 |

7 | PikMike | 152 |

8 | Ashishgup | 151 |

8 | Petr | 151 |

10 | 300iq | 150 |

I recently spotted this problem of IOI 2018. I couldn't come up with a proper approach. Only thing that I know is the solution is associated with graph. Can you please help me to solve this problem?

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/15/2018 08:19:13 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

You can find the solution here

The best part is you don't create the above graph explicitly. You calculate the graph on the fly form the original one. And most graph algorithm actually uses another implicit graph which is calculated on the fly (yes, Dijkstra too).