淦,为什么别人都是wa,或者TLE,唯独我是MLE
查看原帖
淦,为什么别人都是wa,或者TLE,唯独我是MLE
177604
LXH5514楼主2021/4/19 20:53

求助大佬,非常玄学

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+f*(c-'0'),c=getchar();
	return x;
}
const int MAXN=5*1e5+10;
int n,m,ans,s,p;
int a[MAXN];
struct node
{
	int u,v;
}b[MAXN];
int cnt;
int first[MAXN],net[MAXN];
int ys[MAXN];
int h[MAXN];
int l[MAXN],tot;
int val[MAXN],bar[MAXN];
int f[MAXN];
void add(int x,int y)
{
	cnt++;
	b[cnt].u=x;
	b[cnt].v=y;
	net[cnt]=first[x];
	first[x]=cnt;
}
void dfs(int x)
{
	if(h[x]==1)return ;
	h[x]=1;
	for(int i=first[x];i;i=net[i])
	dfs(b[i].v);
	l[++tot]=x;
}
void dfs1(int x)
{
	if(h[x]>0)return ;
	h[x]=tot;
	for(int i=first[x];i;i=net[i])
	dfs1(b[i].u);
}
void tp()
{
	queue<int>q;
	q.push(s);
	f[s]=val[s];
	while(!q.empty())
	{
		int k=q.front();
		q.pop();
		for(int i=first[k];i;i=net[i])
		{
			f[b[i].v]=max(f[b[i].v],f[k]+val[b[i].v]);
			if(bar[b[i].v]==1)ans=max(ans,f[b[i].v]);
			q.push(b[i].v);
		}
	}
}
signed main()
{
//	freopen("p3627_2.in","r",stdin); 
	n=read();
//	cout<<n<<endl;
	m=read();
	for(int i=1;i<=m;i++)
	{
		int x,y;
		x=read();
		y=read();
		add(x,y);
	}
	cnt=0;
	for(int i=1;i<=n;i++)
	a[i]=read();
	s=read();
	p=read();
	for(int i=1;i<=p;i++)
	{
		int x=read();
		ys[x]=1;
	}
	for(int i=1;i<=n;i++)
	if(h[i]==0)dfs(i);
	for(int i=1;i<=n;i++)
	first[i]=0,h[i]=0;
	for(int i=1;i<=m;i++)
	{
		net[i]=first[b[i].v];
		first[b[i].v]=i;
	}
	tot=0;
	for(int i=n;i>=1;i--)
	{
		if(h[l[i]]==0)
		{
			tot++;
			dfs1(l[i]);
		}
	}
	s=h[s];
	for(int i=1;i<=n;i++)
	val[h[i]]+=a[i],bar[h[i]]=bar[h[i]]|ys[i];
	for(int i=1;i<=tot;i++)
	first[i]=0;
	for(int i=1;i<=m;i++)
	{
		if(h[b[i].u]==h[b[i].v])continue;
		add(h[b[i].u],h[b[i].v]);
	}
	tp();
	printf("%d\n",ans);
 	return 0;
}
2021/4/19 20:53
加载中...