「Summary」2022-07-04 做题记录

🤡

2022-07-04

$\mathbb{Network}$

link

本人，一个把数据范围看错硬刚树剖的蠢货。

做法很简单，首先边双缩点，变成树，对于每次加一条边 $(u, v)$ ，则树上两点之间的所有割边全部清除，把每条割边的权转到割边的终点上来，然后就可以用树剖或并查集维护。

其实观察数据范围就知道可以直接暴力跳，根本不用树剖或者并查集。

时间复杂度 $\Theta(nq)$ （暴力），$\Theta(q\log_2n)$ （树剖）。

结果我写完出现一堆锅。关于写挂的原因，详情见 G-submissions 。

$\mathbb{Falling \ Sand \ (Easy \ Version)}$

link

笑了，脑抽又把 $i,j$ 写反了。。。

发现干扰的方向并不是双向的，这个可以预处理出来一个点对其他的干扰。
在往下掉的时候只需要处理到距离它最近的一个沙块即可。
得到一堆 $scc$ ，缩点后连边，判出入度，统计入读为 $0$ 的 $scc$ 的个数即是答案。

$\mathbb{Data \ Center \ Drama}$

link

witcon : 你是没有学过当前弧优化吗？

显而易见的贪心，把给定的图中的奇数入度点都两两连边。
如果边数还是奇数的话，那就连一个自环 $(1, 1)$。
最后输出的时候，输出一条边就换一次向。

然后不删边的🐖被卡 TLE 了。。。
然后把 vector 换成了链式前向星。