60pts求调(感觉思路没错)
查看原帖
60pts求调(感觉思路没错)
1122271
zhouyirana楼主2025/1/17 20:37
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N=5e5+10,MOD=998244353;
int n,m;
ll k;
ll ans[N];
ll num[N];
ll a[N];
vector<int>e[N];
vector<int>e2[N];
ll v[N];
void bfs()
{
  bool vis[N];
  queue<pair<int,int> >q;
  for(int i=1;i<=m;i++)
  {
  	q.push(make_pair(v[i],1));
  	vis[v[i]]=1;
  }
  while(!q.empty())
  {
  	pair<int,int>t;
  	t=q.front();
  	q.pop();
  	num[t.first]=k-t.second+1;
  	for(int i=0;i<e[t.first].size();i++)
  	{
  	  if(!vis[e[t.first][i]])
  	  {
  	  	q.push(make_pair(e[t.first][i],t.second+1));
  	  	vis[e[t.first][i]]=1;
	  }
	}
  }
}
int main()
{
	scanf("%d%lld%d",&n,&k,&m);
	for(int i=1;i<=m;i++)
	  scanf("%lld",&v[i]);
	for(int i=1;i<=n;i++)
	{
	  scanf("%lld",&a[i]);
	  for(int j=1;j<=a[i];j++)
	  {
	    int x;
	    scanf("%d",&x);
	    e[i].push_back(x);
	    e2[x].push_back(i);
	  }
	}
    bfs();
    /*
    for(int i=1;i<=n;i++)
      printf("%lld ",num[i]);
    */
    for(int i=1;i<=n;i++)
    {
      ans[i]+=(1ll*((num[i])%MOD)*((a[i])%MOD))%MOD;
      ans[i]%=MOD;
	}
	for(int i=1;i<=m;i++)
	{
	  ans[v[i]]+=(k%MOD);
	  ans[v[i]]%=MOD;
	}
	for(int i=1;i<=n;i++)
	{
	  for(int j=0;j<e2[i].size();j++)
	  {
	  	if(num[e2[i][j]]<=0)  continue;
	  	ans[i]+=((num[e2[i][j]])-1)%MOD;
	    ans[i]%=MOD;
	  }
	}
	for(int i=1;i<=n;i++)
	  printf("%lld ",ans[i]%MOD);
	printf("\n");
	return 0;
}
2025/1/17 20:37
加载中...