记录编号	390570	评测结果	AAAAAAAAAA
题目名称	[SDOI 2010] 所驼门王的宝藏	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.689 s
提交时间	2017-04-03 13:18:31	内存使用	12.23 MiB

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int N=1e5+10,SIZE=1e6+10;
typedef pair<int,int> pr;
int n,R,C,x[N],y[N],tp[N];
struct node{
	int v;node *next;
	node(int V){v=V;next=0;}
};
struct queue{
	node *head;
	void push(int x){
		node *y=new node(x);
		y->next=head;
		head=y;
	}
};
queue E[N],r[SIZE],c[SIZE];
map<pr,int> M;
int stack[N],top,dfn[N],low[N],fa[N],size[N],ans;
bool ins[N];
void tarjan(int x){
	static int cnt=0;
	dfn[x]=low[x]=++cnt;
	ins[stack[++top]=x]=1;
	for (node* i=E[x].head;i;i=i->next){
		int v=i->v;
		if (!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);else
		if (ins[v]) low[x]=min(low[x],dfn[v]);
	}
	if (low[x]==dfn[x]){
		while (stack[top]!=x){
			int i=stack[top--];
			ins[i]=0;fa[i]=x;size[x]++;
		}
		ins[stack[top--]]=0;fa[x]=x;size[x]++;
	}
}
queue go[N];
int dp[N];//dp[i]表示走到i号联通块后最多访问多少节点
int val(int x){
	if (dp[x]) return dp[x];
	for (node* i=go[x].head;i;i=i->next)
		dp[x]=max(dp[x],val(i->v));
	return dp[x]+=size[x];
}
int main()
{
	freopen("sdoi10sotomon.in","r",stdin);
	freopen("sdoi10sotomon.out","w",stdout);
	scanf("%d%d%d",&n,&R,&C);
	for (int i=1;i<=n;i++){
		scanf("%d%d%d",&x[i],&y[i],&tp[i]);
		M[pr(x[i],y[i])]=i;
		r[x[i]].push(i);
		c[y[i]].push(i);
	}
	for (int i=1;i<=n;i++){
		if (tp[i]==1){
			for (node* j=r[x[i]].head;j;j=j->next)
				E[i].push(j->v);
		}
		if (tp[i]==2){
			for (node* j=c[y[i]].head;j;j=j->next)
				E[i].push(j->v);
		}
		if (tp[i]==3){
			for (int a=-1;a<=1;a++)
			for (int b=-1;b<=1;b++){
				pr now(x[i]+a,y[i]+b);
				if (M.count(now)) E[i].push(M[now]); 
			}
		}
	}
	for (int i=1;i<=n;i++)
		if (!dfn[i]) tarjan(i);
	for (int i=1;i<=n;i++)
	for	(node* j=E[i].head;j;j=j->next){
		int v=fa[j->v];
		if (fa[i]!=v) go[fa[i]].push(v);
	}
	for (int i=1;i<=n;i++) ans=max(ans,val(i));
	printf("%d\n",ans);
	return 0;
}