XIX Open Cup named after E.V. Pankratiev. Grand Prix of Eurasia, Division 1.

A B CDE F GHIJK

复盘人：rxd

开场散开看题。我看了P8，gt看了P4，叶队看了P5。

然后叶队上机快速过了P5。

0h9min：P5（+0）。

gt给我讲了下P4的题意，我们讨论了下，大概是可以bitset。然后gt去看P1，我继续看P8了。

0h23min：P1（+0）。

0h29min：P8（+0）。

P4空间不太够，需要动态开点，我又想了5分钟P4有没有简单做法，感觉没有就开写了。我写的时候叶队给gt讲了下P7做法。

0h46min：P4（+0）。

然后叶队给我讲了下P7做法，我来写。一开始以为写写挺快的，但实际上写了一年。这期间叶队会了P11，然后他们各自开别的题去了。

1h42min：P7（+0）。

叶队写P11。gt给我讲了P3、P9、P10，大概都是傻逼手速题。叶队眼调P11的时候我写P3。

2h09min：P11（+0）。

2h13min：P3（+0）。

P9有点犹豫要不要直接double上了，莽了一发然后过了有点爽。

2h32min：P9（+0）。

我写P10的时候他们两个在搞最后两个题P2和P6。P10一开始题意里有个细节搞错了WA了一发。中途OJ又疯狂宕机，好久才交得上去。

3h26min：P10（+1）。

之后我看了下P2的题意，然后划了。

P1：

P2：

P3：最大流。

P4：每个连通块维护个bitset表示它有哪些限制。询问的时候两个bitset AND一下看看是否为空。合并就直接或起来。考虑把这个过程动态开点，即用线段树维护bitset，合并的时候线段树合并，这样时间仍为\(O(\frac{n^2}{32})\)，空间变成\(O(n \log n)\)。

P5：

P6：

P7：每个东西的答案一定在下凸壳斜率为负的部分上。拿个堆，把所有下凸壳从右往左退一下就可以了。

P8：二分答案计算。

P9：线段树，直接把坐标*10^6当成整数做就行了。读入也直接double读入。

P10：直接以（轮数，能量）为双关键字来Dijkstra就行了。注意最后一轮如果能量用完了，新开的那一轮不应该算到答案里。

P11：

总结(by rxd)：

优点：dirt比较少。

缺点：做题顺序可以再调整，手速可以再快点。最后两个题别划。