Hi, does anyone know a solution to this problem? I saw some contestants' solutions, but I'm not able to understand everything just from the code.

Thanks

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

1 | tourist | 3775 |

2 | Benq | 3724 |

3 | orzdevinwang | 3697 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | cnnfls_csy | 3620 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

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

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 163 |

5 | maroonrk | 162 |

6 | SecondThread | 159 |

7 | nor | 158 |

8 | -is-this-fft- | 153 |

9 | kostka | 146 |

10 | TheScrasse | 144 |

Hi, does anyone know a solution to this problem? I saw some contestants' solutions, but I'm not able to understand everything just from the code.

Thanks

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/03/2023 16:55:46 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

First, we use DSU in order to store current companies after each merge. For each company we also store a map: the degree of the root (at most D) to the minimal depth of the tree with that degree. Initially all trees contain 1 vertex and all maps contain the pair (0, 1) only. Calculating this map for a new company after merge is simple: we just trying to connect the first root to the second one and vice versa, for all values of the degree of parent root. In a such way the new degree is increased by 1 and the new depth is at most the minimal depth of child root's tree increased by 1.