同样的一份代码在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;
}
有没有人知道一般出现这种情况是什么原因,应该如何解决?
求求了