bzoj AC,luogu TLE是怎么回事呢?
查看原帖
bzoj AC,luogu TLE是怎么回事呢?
220857
素质玩家孙1超楼主2020/6/6 12:49

同样的一份代码在bzoj上跑总共只要3200ms,在darkbzoj上跑最大的一个数据点跑了655ms,可是在luogu却tle了第二个点,这大概是什么原因呢?

代码:

#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include <tr1/unordered_map>
#include<utility>
//#include<map>
#define pii pair<int,int > 
#define For(pos) for(register int k=First[pos];k;k=Next[k])
#define mp make_pair
const int dx[]={1,1,1,0,0,-1,-1,-1};
const int dy[]={1,0,-1,1,-1,1,0,-1};
using namespace std;
using namespace std::tr1;
inline int R()
{
	char c;int sign=1,res=0;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1;res+=c-'0';
	while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
	return res*sign;	
}
const int Maxn=6e5+5;
struct pairhash	{    template<class T1, class T2>    size_t operator() (const pair<T1, T2> &x) const    {        hash<T1> h1;        hash<T2> h2;        return h1(x.first) ^ h2(x.second);    }	};
unordered_map<pii,int,pairhash>q; 
vector<int>e[Maxn];
struct point 
{
	int x,y,op,num; 
}a[Maxn];
bool cmp1(point A,point B)
{
	return A.x<B.x;
}
bool cmp2(point A,point B)
{
	return A.y<B.y;
}
int n,col1[Maxn],size1[Maxn],sum,st1[Maxn],top1,First[Maxn],to[Maxn*2],Next[Maxn*2],cnt,From[Maxn*2];
int dfn[Maxn],low[Maxn],col2[Maxn],sum2,size2[Maxn],ind[Maxn],st2[Maxn],top2,r,c,dp[Maxn];
queue<int>que;
bool vis[Maxn];
inline void add(int z,int y)
{
	Next[++cnt]=First[z];
	First[z]=cnt;
	to[cnt]=y;From[cnt]=z;
} 
void tarjan(int pos)
{
	dfn[pos]=low[pos]=++dfn[0];
	st1[++top1]=pos;vis[pos]=1;
	For(pos)
	{
		if(!dfn[to[k]])
		{
			tarjan(to[k]);
			low[pos]=min(low[pos],low[to[k]]);
		}
		else if(vis[to[k]]) low[pos]=min(low[pos],dfn[to[k]]); 
	}
	if(low[pos]==dfn[pos])
	{
		++sum2;
		while(st1[top1]!=pos)
		{
			col2[st1[top1]]=sum2;
			size2[sum2]+=size1[st1[top1]];
			vis[st1[top1--]]=0; 
		}
		col2[st1[top1]]=sum2;
		size2[sum2]+=size1[st1[top1]];
		vis[st1[top1--]]=0;
	} 
} 
int main()
{;
//	freopen("sotomon.in","r",stdin);
	
	n=R();r=R();c=R();
	for(int i=1;i<=n;i++)
	{
		a[i].x=R();
		a[i].y=R();
		a[i].op=R();
		a[i].num=i+n;
		q[mp(a[i].x,a[i].y)]=i+n;
	}
	sort(a+1,a+1+n,cmp1);
	for(int i=1;i<=n;i++)
	{
		if(a[i].x!=a[i-1].x)
		{
			if(top1)
			{
				++sum;
				size1[sum]=top1;
				while(top1)
					col1[st1[top1--]]=sum;
//				while(top2)
//					add(sum,st2[top2--]);
			}
			top1=0;
			top2=0;
		}
		if(a[i].op==1)
			st1[++top1]=a[i].num;
		else st2[++top2]=a[i].num; 
	}
	if(top1)
	{
		++sum;
		size1[sum]=top1;
		while(top1)
			col1[st1[top1--]]=sum;
//		while(top2)
//			add(sum,st2[top2--]);
	}
	top1=0;
	top2=0;
	sort(a+1,a+1+n,cmp2);
	for(int i=1;i<=n;i++)
	{
		if(a[i].y!=a[i-1].y)
		{
			if(top1)
			{
				++sum;
				size1[sum]=top1;
				while(top1)
					col1[st1[top1--]]=sum;
//				while(top2)
//					add(sum,st2[top2--]);
			}
			top1=0;
			top2=0;
		}
		if(a[i].op==2)
			st1[++top1]=a[i].num;
		else st2[++top2]=a[i].num; 
	}
	if(top1)
	{
		++sum;
		size1[sum]=top1;
		while(top1)
			col1[st1[top1--]]=sum;
//		while(top2)
//			add(sum,st2[top2--]);
	}
	top1=0;
	top2=0;
	for(int i=1;i<=n;i++)
		if(a[i].op==3)
		{
			col1[a[i].num]=++sum;
			size1[sum]=1;
		}
//-----------
	sum=0;
	sort(a+1,a+1+n,cmp1);
	for(int i=1;i<=n;i++)
	{
		if(a[i].x!=a[i-1].x)
		{
			if(top1)
			{
				++sum;
//				size1[sum]=top1;
//				while(top1)
//					col1[st1[top1--]]=sum;
				while(top2)
					add(sum,col1[st2[top2--]]);
			}
			top1=0;
			top2=0;
		}
		if(a[i].op==1)
			st1[++top1]=a[i].num;
		else st2[++top2]=a[i].num; 
	}
	if(top1)
	{
		++sum;
//		size1[sum]=top1;
//		while(top1)
//			col1[st1[top1--]]=sum;
		while(top2)
			add(sum,col1[st2[top2--]]);
	}
	top1=0;
	top2=0;
	sort(a+1,a+1+n,cmp2);
	for(int i=1;i<=n;i++)
	{
		if(a[i].y!=a[i-1].y)
		{
			if(top1)
			{
				++sum;
//				size1[sum]=top1;
//				while(top1)
//					col1[st1[top1--]]=sum;
				while(top2)
					add(sum,col1[st2[top2--]]);
			}
			top1=0;
			top2=0;
		}
		if(a[i].op==2)
			st1[++top1]=a[i].num;
		else st2[++top2]=a[i].num; 
	}
	if(top1)
	{
		++sum;
//		size1[sum]=top1;
//		while(top1)
//			col1[st1[top1--]]=sum;
		while(top2)
				add(sum,col1[st2[top2--]]);
	}
	top1=0;
	top2=0;
		for(int i=1;i<=n;i++)
		if(a[i].op==3)
		{
			++sum;
		//	col1[a[i].num]=++sum;
		//	size1[sum]=1;
		}
	for(int i=1;i<=n;i++)
		if(a[i].op==3)
		{
			for(int k=0;k<9;k++)
			{
				pii tmp=make_pair(a[i].x+dx[k],a[i].y+dy[k]);
				int To=q[tmp];
				if(!To) continue;
				add(col1[a[i].num],col1[To]);
			}
		}
	top1=0;
	for(int i=1;i<=sum;i++)
	if(!dfn[i])
	tarjan(i);
	for(int k=1;k<=cnt;k++)
	{
		if(col2[From[k]]!=col2[to[k]])
		{
			e[col2[From[k]]].push_back(col2[to[k]]);
			ind[col2[to[k]]]++;
		}
	}
	for(int i=1;i<=sum2;i++)
		if(!ind[i]) que.push(i);
	int ans=0;
	while(!que.empty())
	{
		int pos=que.front();
		que.pop();ans=max(ans,dp[pos]+size2[pos]);
		for(int i=0;i<e[pos].size();i++)
		{
			ind[e[pos][i]]--;
			dp[e[pos][i]]=max(dp[e[pos][i]],dp[pos]+size2[pos]);
			if(!ind[e[pos][i]])que.push(e[pos][i]);
		}
	}
	printf("%d\n",ans);
	return 0;
}

有没有人知道一般出现这种情况是什么原因,应该如何解决?

求求了

2020/6/6 12:49
加载中...