老子是北瓜 @ 2021-08-24 20:24:17
百分之百肯定是主函数中拓扑排序的部分写错了,但是不知道还有什么情况没有考虑到,求大佬帮忙看看,万分感谢!
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<vector>
#define N 1000005
#define mod 998244353
using namespace std;
int n,m,in[N],type[N],p[N],sz,T;
long long mul[N],a[N],val[N],q[N],times[N];
bool vis[N];
vector<int> g[N];
void dfs1(int u)
{
if(type[u]==2)
{
mul[u]=mul[u]*val[u]%mod;
return ;
}
if(type[u]==3)
{
for(int i=0; i<g[u].size(); ++i)
{
int v=g[u][i];
if(vis[v]==0){
vis[v]=1;
dfs1(v);
}
mul[u]=mul[u]*mul[v]%mod;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; ++i)
scanf("%lld",&a[i]);
scanf("%d",&m);
for(int i=1; i<=m; ++i)
{
scanf("%d",&type[i]);
if(type[i]==1) scanf("%d%lld",&p[i],&val[i]);
if(type[i]==2) scanf("%lld",&val[i]);
if(type[i]==3)
{
scanf("%d",&sz);
int tmp;
for(int j=1; j<=sz; ++j)
{
scanf("%d",&tmp);
g[i].push_back(tmp);
++in[tmp];
}
}
}
scanf("%d",&T);
++m;
type[m]=3;
for(int i=1; i<=T; ++i)
{
int tmp;
scanf("%d",&tmp);
g[m].push_back(tmp);
++in[tmp];
}
for(int i=1; i<=m; ++i)
mul[i]=1;
vis[m]=1;
dfs1(m);
for(int i=1; i<=n; ++i)
a[i]=a[i]*mul[m]%mod;
int l=0,r=0;
for(int i=m; i>=1; --i)
if(in[i]==0)
q[++r]=i;
times[m]=1;
while(l<r)
{
++l;
int u=q[l];
long long w=times[u];
for(int i=g[u].size()-1; i>=0; --i)
{
int v=g[u][i];
--in[v];
times[v] += w;
if(type[v]==1) a[p[v]]=(a[p[v]] + val[v]*w%mod)%mod;
if(type[v]==3 && in[v]==0) q[++r]=v;
w=w*mul[v]%mod;
}
}
for(int i=1; i<=n; ++i)
cout<<a[i]<<" ";
return 0;
}
by 老子是北瓜 @ 2021-08-24 20:26:10
打错了,是75pts
by 老子是北瓜 @ 2021-08-24 21:38:24
找到原因了
times[v] += w;
没膜,淦!