Quiz
https://codeforces.com/contest/1206/problem/D
- 2000人が解いているので解けなきゃいけない
Submit
なし
解法
- https://codeforces.com/blog/entry/69158
- まず、ビットで考えた時に同じビット位置が１のものが３つ存在したら、サイクルの長さ３で終了
- それ以外の場合、同じビット位置が１のものの数は多くても２
- a=1018なので、ビットは60桁まで考えれば十分で、エッジの数も60以下となり、グラフはとても小さい
- 以下を考える
- この場合、最小のサイクルは４
- これをどう見つけるかだが、各エッジ edge(u, v) を切ってみて、それでもu-v間にinf以外の最短距離があるか調べる
- 最短距離がある場合
- サイクルの長さ = 最短距離 + 1
- 最短距離がない(inf)場合
- そのエッジはサイクルと関係ない
- よって、求めることができました
