/ Randle /

记录详情

Runtime Error


  
# 状态 耗时 内存占用
#1 Accepted 126ms 38.375 MiB
#2 Accepted 126ms 38.125 MiB
#3 Accepted 123ms 35.125 MiB
#4 Accepted 124ms 38.203 MiB
#5 Accepted 120ms 37.949 MiB
#6 Accepted 125ms 35.633 MiB
#7 Accepted 122ms 35.0 MiB
#8 Accepted 123ms 37.0 MiB
#9 Accepted 23ms 36.25 MiB
#10 Accepted 22ms 36.875 MiB
#11 Accepted 43ms 39.684 MiB
#12 Accepted 49ms 39.75 MiB
#13 Accepted 19ms 36.0 MiB
#14 Runtime Error 273ms 47.617 MiB
#15 Accepted 357ms 51.125 MiB
#16 Accepted 288ms 50.738 MiB
#17 Accepted 273ms 51.25 MiB
#18 Accepted 2248ms 49.461 MiB
#19 Accepted 1848ms 49.566 MiB
#20 Accepted 1748ms 49.418 MiB

代码

#include<bits/stdc++.h>
inline void read(int&a)
{
	a=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
}
inline void write(int a)
{
	if(a<0){putchar('-');a=-a;}
	if(a>9)write(a/10);
	putchar(a%10+'0');
}
const int maxn=1e6+1;
int next1[maxn],dfn[maxn],low[maxn],to1[maxn],point1[maxn],from1[maxn];
int n,m,r=0,d=0;
bool vis[maxn];
inline void add1(int a,int b)
{
	next1[++r]=point1[a];
	to1[r]=b;from1[r]=a;
	point1[a]=r;
}
int in[maxn],next[maxn],to[maxn],point[maxn],from[maxn];
inline void add(int a,int b)
{
	++in[b];
	next[++d]=point[a];
	to[d]=b;
	point[a]=d;
}
int tt,f[maxn],ans=0;
int stack[maxn],belong[maxn],end=0,value[maxn];
bool in_stack[maxn];
inline void tarjan(int p)
{
	
	vis[p]=true;
	dfn[p]=low[p]=++tt;
	value[p]=1;
	int side=point1[p];
	while(side)
	{
		if(!vis[to1[side]])
		{
			stack[++end]=to1[side];
			in_stack[to1[side]]=true;
			tarjan(to1[side]);
			low[p]=std::min(low[p],low[to1[side]]);
		}
		else if(in_stack[to1[side]])
		{
			low[p]=std::min(low[p],low[to1[side]]);
		}
		side=next1[side];
	}
	if(dfn[p]==low[p])
	{
		while(stack[end]!=p)
		{
			belong[stack[end]]=p;
			in_stack[stack[end]]=false;
			value[p]+=value[stack[end]];
			--end;
		}
		belong[p]=p;
		in_stack[p]=false;
		--end;
	}
}
inline void dfs(int p)
{
	int side=point[p];
	while(side)
	{
		if(f[p]+value[to[side]]>f[to[side]])
			{f[to[side]]=f[p]+value[to[side]];dfs(to[side]);}
		side=next[side];
	}
}
int main()
{
	read(n);read(m);
	memset(in,0,sizeof(in));
	memset(value,0,sizeof(value));
	memset(in_stack,false,sizeof(in_stack));
	memset(vis,false,sizeof(vis));
	memset(point1,0,sizeof(point1));
	int u,v;
	for(int i=1;i<=m;i++)
	{
		read(u);read(v);
		add1(u,v);
	}
	tt=0;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			stack[++end]=i;in_stack[i]=true;
			tarjan(i);
		}
	}
	for(int i=1;i<=r;i++)if(belong[from1[i]]!=belong[to1[i]])add(belong[from1[i]],belong[to1[i]]);
	for(int i=1;i<=n;i++)if(!in[i]&&belong[i]==i){f[i]=value[i];dfs(i);}
	for(int i=1;i<=n;i++)ans=std::max(ans,f[i]);
	write(ans);
	return 0;
}

信息

递交者
类型
递交
题目
BOMB炸弹(CQ直辖市noip模拟赛联考) T1
题目数据
下载
语言
C++
递交时间
2017-11-04 20:12:21
评测时间
2017-11-04 20:12:21
评测机
分数
95
总耗时
8190ms
峰值内存
51.25 MiB