记录编号	459264	评测结果	AAAAAAAAAA
题目名称	[SDOI 2010] 所驼门王的宝藏	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	0.642 s
提交时间	2017-10-12 20:49:32	内存使用	119.81 MiB

#pragma GCC optimize("O3")
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector> 
#define N 100105
using namespace std;
int read()
{
	int sum=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9'){sum=(sum<<3)+(sum<<1)+x-'0';x=getchar();}
	return sum*f;
}
struct road{int u,v,next;}lu[N*40],l[N*40];
int s,n,m,e,E,adj[N],adj_[N],in[N],f[N];
int cnt,dfn[N],low[N];
int head,inzhan[N],zhan[N];
int tot,belong[N],sum[N];
struct node{int x,y,t;}a[N];
vector<int> hx[1000105],zx[1000105];
void add(int u,int v){lu[++e]=(road){u,v,adj[u]};adj[u]=e;}
void tarjan(int x)
{
	dfn[x]=low[x]=++cnt;
	inzhan[x]=1;zhan[++head]=x;
	for(int i=adj[x];i;i=lu[i].next)
	{
		int to=lu[i].v;
		if(!dfn[to])
		{
			tarjan(to);
			low[x]=min(low[x],low[to]);
		}
		else
			if(inzhan[to])low[x]=min(low[x],dfn[to]);
	}
	if(low[x]==dfn[x])
	{
		tot++;int tmp,s=0;
		while(1)
		{
			s++;
			tmp=zhan[head--];
			inzhan[tmp]=0;
			belong[tmp]=tot;
			if(tmp==x)break;
		}
		sum[tot]=s;
	}
}
int dfs(int x,int fa)
{
	if(f[x])return f[x];
	for(int i=adj_[x];i;i=l[i].next)
	{
		int to=l[i].v;if(to==fa)continue;
		f[x]=max(f[x],dfs(to,x));
	}
	return f[x]=f[x]+sum[x];
}
int main()
{
	freopen("sdoi10sotomon.in","r",stdin);
	freopen("sdoi10sotomon.out","w",stdout);
	s=read();n=read();m=read();
	for(int i=1;i<=s;i++)
	{
		a[i].x=read(),a[i].y=read(),a[i].t=read();
		hx[a[i].x].push_back(i);
		zx[a[i].y].push_back(i);
	}
	for(int i=1;i<=s;i++)
	{
		if(a[i].t==1)
		{
			int len=hx[a[i].x].size();
			for(int j=0;j<len;j++)
			{
				int x=hx[a[i].x][j];
				if(x==i)continue;
				add(i,x);
			}
		}
		else
		if(a[i].t==2)
		{
			int len=zx[a[i].y].size();
			for(int j=0;j<len;j++)
			{
				int x=zx[a[i].y][j];
				if(x==i)continue;
				add(i,x);
			}
		}
		else
		if(a[i].t==3)
		{
			int len;
			len=hx[a[i].x-1].size();
			for(int j=0;j<len;j++)
			{
				int x=hx[a[i].x-1][j],y=a[x].y-a[i].y;
				if(x==i||y<-1||y>1)continue;
				add(i,x);
			}
			len=hx[a[i].x].size();
			for(int j=0;j<len;j++)
			{
				int x=hx[a[i].x][j],y=a[x].y-a[i].y;
				if(x==i||y<-1||y>1)continue;
				add(i,x);
			}
			len=hx[a[i].x+1].size();
			for(int j=0;j<len;j++)
			{
				int x=hx[a[i].x+1][j],y=a[x].y-a[i].y;
				if(x==i||y<-1||y>1)continue;
				add(i,x);
			}
		}
	}
	for(int i=1;i<=s;i++)
		if(!dfn[i])tarjan(i);
	for(int i=1;i<=e;i++)
	{
		int u=lu[i].u,v=lu[i].v;
		if(belong[u]==belong[v])continue;
		int x=belong[u],y=belong[v];
		l[++E]=(road){x,y,adj_[x]};adj_[x]=E;
		in[y]++;
	}
	int ans=0;
	for(int i=1;i<=tot;i++)
		ans=max(ans,dfs(i,0));
	printf("%d",ans);
}