专栏文章

【题解】P11915 [PA 2025] 瞬间传送 / Teleport

SStarrykiller暁美 ほむら
P11915题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipv6d7j
此快照首次捕获于
2025/12/03 18:28
3 个月前
此快照最后确认于
2025/12/03 18:28
3 个月前
查看原文
O(n4log⁡n/w)\mathcal{O}(n^4\log n/w) 做法。但是常数非常小，实际表现很好。
考虑二分答案 ll，枚举加入的边 (u,v)(u,v)。
如果不合法，那么必然存在一对 s,ts,t，使得 dist⁡′(s,t)≥l+1\operatorname{dist}'(s,t)\ge l+1。
预处理出原图的 dist⁡\operatorname{dist}，枚举 ss。如果 tt 不合法，那么必须满足：
  • dist⁡(s,t)≥l+1\operatorname{dist}(s,t)\ge l+1；
  • dist⁡(s,u)+dist⁡(v,t)≥l+1  ⟹  dist⁡(v,t)≥l−dist⁡(s,u)+1\operatorname{dist}(s,u)+\operatorname{dist}(v,t)\ge l+1\implies \operatorname{dist}(v,t)\ge l-\operatorname{dist}(s,u)+1；
  • dist⁡(s,v)+dist⁡(u,t)≥l+1  ⟹  dist⁡(u,t)≥l−dist⁡(s,v)+1\operatorname{dist}(s,v)+\operatorname{dist}(u,t)\ge l+1\implies \operatorname{dist}(u,t)\ge l-\operatorname{dist}(s,v)+1。
我们枚举了 u,v,su,v,s。我们可以预处理 f(u,i)={v:dist⁡(u,v)≥i}f(u,i)=\{v:\operatorname{dist}(u,v)\ge i\}，这样判定的时候只需要判定三个集合交集是否非空。
使用 bitset\texttt{bitset} 维护集合，时间复杂度即为 O(n3⋅n/w⋅log⁡n)=O(n4log⁡n/w)\mathcal{O}(n^3\cdot n/w \cdot \log n)=\mathcal{O}(n^4 \log n / w)。
有一个显然的剪枝：如果 (u,v)(u,v) 已经合法，直接返回 true 即可。这样在官方数据下跑得飞快。（如果不加这个剪枝，在洛谷上依然可以通过。）
赛时担心被卡加了随机化打乱点权，在洛谷上运行时间为 311 ms\text{311 ms}。
如果有人能够提供在随机化下能够几乎一定将本做法卡到复杂度上界的数据，欢迎联系我。
CPP
auto check=[&](int L) {
    for (int u=0; u<n; ++u)
        for (int v=u+1; v<n; ++v) {
            bool flag=true;
            for (int s=0; s<n; ++s) {
                // dis[s][t]>=L+1
                // dis[v][t]>=L+1-dis[s][u]
                // dis[u][t]>=L+1-dis[s][v]
                int a=max(0,L+1-dis[s][u]), b=max(0,L+1-dis[s][v]);
                if ((f[s][L+1]&f[v][a]&f[u][b]).any()) {
                    flag=false; break;
                }
            }
            if (flag) return true;
        }
    return false;
};

int l=0, r=(n+1)/2;
while (l<r) {
    int mid=(l+r)>>1;
    if (check(mid)) r=mid;
    else l=mid+1;
}
cout<<l<<'\n';

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...