QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#570723#8836. Highway HoaxDjangle162857WA 3ms32420kbC++142.1kb2024-09-17 17:22:162024-09-17 17:22:17

Judging History

你现在查看的是最新测评结果

  • [2024-09-17 17:22:17]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:32420kb
  • [2024-09-17 17:22:16]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<set>
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

const int N=400010;
const int mod=998244353;
int n,cnt,maxicnt,c[N],f[N][2],nouid[N],vis[N];
vector<int>id[N],e2[N];
char s[N];

struct Graph{
	int tot,head[N],suiv[N],ver[N];

	inline void lnk(int x,int y)
	{
		ver[++tot]=y;
		suiv[tot]=head[x];
		head[x]=tot;
	}

	inline void bfs(int st,int posid)
	{
		queue<int>q;
		q.push(st);
		while(q.size())
		{
			int x=q.front();q.pop();
			id[x].push_back(posid);
			c[posid]++;
			for(int i=head[x];i;i=suiv[i])
			{
				int y=ver[i];
				if(s[y]!='S')continue;
				if(id[y].size()&&!nouid[y])
					nouid[y]=++cnt;
				q.push(y);
			}
		}
	}

	inline void dfs(int x,int fa)
	{
		vis[x]=1;
		for(auto y:e2[x])
		{
			if(y==fa)continue;
			dfs(y,x);
		}
		
		if(x<=maxicnt)
		{
			f[x][0]=c[x]-1;
			f[x][1]=1;
			for(auto y:e2[x])
			{
				if(y==fa)continue;
				int tem0=f[x][0],tem1=f[x][1];
				f[x][0]=1ll*tem0*f[y][0]%mod;
				f[x][1]=(1ll*tem0*f[y][1]%mod+1ll*tem1*f[y][0]%mod)%mod;

			}

		}
		else
		{
			f[x][0]=1;
			f[x][1]=0;
			for(auto y:e2[x])
			{
				if(y==fa)continue;
				int tem0=f[x][0],tem1=f[x][1];
				f[x][0]=1ll*tem0*f[y][0]%mod;
				f[x][1]=(1ll*tem0*f[y][1]%mod+1ll*tem1*f[y][0]%mod)%mod;

			}
		}
		//cout<<"dfs "<<x<<" "<<f[x][0]<<" "<<f[x][1]<<endl;
	}

}e;

int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1,x,y;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		e.lnk(y,x);
	}
	for(int i=1;i<=n;i++)
		if(s[i]=='F')nouid[i]=++cnt;
	maxicnt=cnt;
	for(int i=1;i<=n;i++)
		if(s[i]=='F')e.bfs(i,nouid[i]);
	cout<<maxicnt<<" "<<cnt<<endl;
	for(int i=1;i<=n;i++)
	{
		if(nouid[i]<=maxicnt)continue;
		for(auto x:id[i])
			e2[x].push_back(nouid[i]),
			e2[nouid[i]].push_back(x)
			//,cout<<"lnk "<<x<<" "<<nouid[i]<<endl
			;
	}
	int ans=1;
	for(int i=1;i<=maxicnt;i++)
		if(!vis[i])
		{
			e.dfs(i,i);
			ans=ans*((f[i][0]+f[i][1])%mod)%mod;
		}
	printf("%d\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 32420kb

input:

5
SFSFS
2 1
2 3
4 3
4 5

output:

2 2
1

result:

wrong answer 1st numbers differ - expected: '1', found: '2'