自动搬运

查看原文

来自洛谷，原作者为

	Moya_Rao 麻烦各位给个关注嘛 qwq 蟹蟹啦 ^_^ || 加 QQ 粉丝群 1039915194 || 五升六女 OIer 一枚，称呼：lucky 猫 / lazy 猫 || 互关 /paste/vicj8uv2，粉福 /article/0hw27gsg

搬运于2025-08-24 23:07:23，当前版本为作者最后更新于2024-12-21 18:18:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可以想到建图，按照 $x$ 数组的释放情况来建一张图，其中 $u$ 指向 $v$ 的边表示每一秒，如果 $u$ 会释放能量，则会释放 $1$ 中子到 $v$ 身上。

可那种自动有中子打击的，怎么办呢？简单，用一个 $0$ 节点连接，就当 $0$ 节点是这个自动的嘛。

不过，每个放射性原子并不是一开始就启动的，如果它还没有启动，那么就不能释放能量，这怎么处理呢？很简单，跑一次洪水填充，把每个节点的启动时间弄出来，就能知道它是什么时候启动的了。至于 $0$ 节点，反正是从它开始跑，它的启动时间就可以被设置成 $0$ 嘛。

但是要特殊处理一个东西：如果 $k$ 过于小，使得某些原子并没有在 $k$ 秒内启动呢？这简单，我选择在一开始赋上一个初值，最后统计答案的时候判断一下即可。

现在就是想如何统计答案了，其实上很简单，可以把答案拆成两部分来算，一部分是题面中所说的 $a_i$，另一部分就是题面中所说的 $b$。

那个什么 $a_i$ 很好算，利用自己的启动时间算出自己会在这 $k$ 秒内活跃多久，拿这个时间乘上 $a_i$ 即可。

$b$ 就相对麻烦一些，它要找到所有连向它的边，依次加上。其实上可以反过来考虑，每遇到一个点 $i$，可以把 $i$ 连向的所有边的答案加到对应节点里去，把这 $n$ 个点遍历完，其实上就行了。

这两个玩意儿，说是说分开算，其实也不然，可以放在一个大的循环里，遍历 $i$ 从 $1$ 到 $n$，每个每个去算就行了。

$0$ 呢？$0$ 也连向了一些点，这些点是无法在刚刚所说的那个循环里计算到的，没什么，多加一个关于 $0$ 的小循环就可以了，看看 $0$ 连向了哪些边，一开始就给它加进去，没什么大碍。

这下，就可以在 $O(n+m)$ 左右的时间内完成，非常快速。不过，千万千万要记得，对 $998244353$ 取模！还有就是，最好写一下快读，否则可能会大大降低其效率！

这里给出一份参考代码，赛时敲的，能 AC，别怀疑。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
const long long mod = 998244353;
long long n,k,m,a[N],t[N],ans[N];
vector<int> g[N];
queue<int> q;
long long read(){
    long long su=0,pp=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')pp=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        su=su*10+ch-'0';
        ch=getchar();
    }
    return su*pp;
}
int main(){
    n=read(),k=read(),m=read();
    for(int i=1;i<=m;i++)g[0].push_back(read());
    for(int i=1;i<=n;i++){
        a[i]=read(),t[i]=k+1;
        for(int j=1;j<=a[i];j++)g[i].push_back(read());
    }
    q.push(0);
    while(!q.empty()){
        int u=q.front();q.pop();
        if(t[u]==k)break;
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(t[v]<=k)continue;
            t[v]=t[u]+1;q.push(v);
        }
    }
    for(int i=0;i<g[0].size();i++){
        int u=g[0][i];
        ans[u]+=k%mod;ans[u]%=mod;
    }
    for(int i=1;i<=n;i++){
        if(t[i]==k+1)continue;
        ans[i]+=(((k-t[i]+1)%mod)*a[i])%mod;ans[i]%=mod;
        for(int j=0;j<g[i].size();j++){
            int u=g[i][j];
            ans[u]+=(k-t[i])%mod;ans[u]%=mod;
        }
    }
    for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
    return 0;
}

如果本篇题解对你有所帮助，请留下一个小小的赞，谢谢！