记录编号	330185	评测结果	AAAAAAATTT
题目名称	[SDOI 2010] 所驼门王的宝藏	最终得分	70
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	4.477 s
提交时间	2016-10-26 07:35:00	内存使用	52.12 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=200010,dx[]={0,0,-1,-1,-1,1,1,1},dy[]={-1,1,0,-1,1,0,-1,1};
struct edge{int to,prev;}e[maxn<<5];
void addedge(int,int,int*);
void Tarjan(int);
int dfs(int);
int n,last[maxn]={0},DAGlast[maxn]={0},len=0,belong[maxn]={0},cnt=0,dfn[maxn]={0},low[maxn],tim=0,s[maxn],top=0,size[maxn],f[maxn]={0},ans=0,u[maxn],v[maxn],d[maxn],x,y;
bool ins[maxn]={false},vis[maxn]={false};
map<int,map<int,int> >a,b;
int main(){
#define MINE
#ifdef MINE
	freopen("sdoi10sotomon.in","r",stdin);
	freopen("sdoi10sotomon.out","w",stdout);
#endif
	int __size__=32<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	scanf("%d%*d%*d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&u[i],&v[i],&d[i]);
		a[u[i]][v[i]]=b[v[i]][u[i]]=i;
	}
	for(int i=1;i<=n;i++){
		if(d[i]==1){
			if(a.count(u[i]))for(map<int,int>::iterator it=a[u[i]].begin();it!=a[u[i]].end();it++)addedge(i,it->second,last);
		}
		else if(d[i]==2){
			if(b.count(v[i]))for(map<int,int>::iterator it=b[v[i]].begin();it!=b[v[i]].end();it++)addedge(i,it->second,last);
		}
		else for(int k=0;k<8;k++){
			x=u[i]+dx[k];
			y=v[i]+dy[k];
			if(a.count(x)&&a[x].count(y))addedge(i,a[x][y],last);
		}
	}
	for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
	for(x=1;x<=n;x++)for(int i=last[x];i;i=e[i].prev)if(belong[e[i].to]!=belong[x])addedge(belong[x],belong[e[i].to],DAGlast);
	for(int i=1;i<=cnt;i++)ans=max(ans,dfs(i));
	printf("%d",ans);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
void addedge(int x,int y,int *last){
	e[++len].to=y;
	e[len].prev=last[x];
	last[x]=len;
}
void Tarjan(int x){
	int y;
	dfn[x]=low[x]=++tim;
	s[++top]=x;
	ins[x]=true;
	for(int i=last[x];i;i=e[i].prev){
		y=e[i].to;
		if(!dfn[y]){
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[y])low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		cnt++;
		do{
			y=s[top--];
			ins[y]=false;
			belong[y]=cnt;
			size[cnt]++;
		}while(x!=y);
	}
}
int dfs(int x){
	if(vis[x])return f[x];
	vis[x]=true;
	for(int i=DAGlast[x];i;i=e[i].prev)f[x]=max(f[x],dfs(e[i].to));
	return f[x]+=size[x];
}