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

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int s,e;
	edge *n;
}*pre[100005],*adj[100005];
typedef pair<int,int> pii;
map<pii,int>ma;
inline void insert(int s,int e){
	edge *tmp(new edge);
	tmp->s=s;
	tmp->e=e;
	tmp->n=pre[s];
	pre[s]=tmp;
}
inline void add(int s,int e){
	edge *tmp(new edge);
	tmp->s=s;
	tmp->e=e;
	tmp->n=adj[s];
	adj[s]=tmp;
}
int n,r,c;
vector<int>hx[1000005];
vector<int>ly[1000005];
int x[100005],y[100005],t[100005];
int cnt,top,qlt,vis[100005],bl[100005],dfn[100005],low[100005],size[100005],sta[100005];
int mov[8][2]={{1,1},{1,0},{1,-1},{0,1},{0,-1},{-1,1},{-1,0},{-1,-1}};
int in[100005];
inline bool check(int x,int y){
	if(x<=0||y<=0||x>r||y>c)return true;
	return false;
}
inline int tarjan(int u){
	dfn[u]=low[u]=++cnt;
	vis[u]=1;
	sta[++top]=u;
	for(edge *i=pre[u];i;i=i->n){
		int e(i->e);
		if(!dfn[e]){
			tarjan(e);
			low[u]=min(low[u],low[e]);
		}
		else
			if(vis[e])
				low[u]=min(low[u],dfn[e]);
	}
	if(low[u]==dfn[u]){
		++qlt;
		int tmp;
		while(1){
			tmp=sta[top--];
			vis[tmp]=0;
			bl[tmp]=qlt;
			if(tmp==u)
				break;
		}
	}
}
inline int dfs(int u){
	vis[u]=cnt;
	int ret(size[u]);
	for(edge *i=adj[u];i;i=i->n){
		int e(i->e);
		if(vis[e]==cnt)continue;
		ret=max(ret,dfs(e)+size[u]);
	}
	vis[u]=0;
	return ret;
}
queue<int>q;
int f[100005];
int main(){
	freopen("sdoi10sotomon.in","r",stdin);
	freopen("sdoi10sotomon.out","w",stdout);
	memset(pre,NULL,sizeof(pre));
	memset(adj,NULL,sizeof(adj));
	n=read(),r=read(),c=read();
	for(int i=1;i<=n;++i){
		x[i]=read(),y[i]=read(),t[i]=read();
		hx[x[i]].push_back(i);
		ly[y[i]].push_back(i);
		ma[pii(x[i],y[i])]=i;
	}
	for(int i=1;i<=n;++i){
		if(t[i]==1){
			int size(hx[x[i]].size());
			for(int j=0;j<size;++j){
				if(hx[x[i]][j]==i)continue;
				insert(i,hx[x[i]][j]);
			}
		}
		if(t[i]==2){
			int size(ly[y[i]].size());
			for(int j=0;j<size;++j){
				if(ly[y[i]][j]==i)continue;
				insert(i,ly[y[i]][j]);
			}
		}
		if(t[i]==3){
			for(int j=0;j<8;++j){
				int tmpx(x[i]+mov[j][0]),tmpy(y[i]+mov[j][1]);
				if(check(tmpx,tmpy)||!ma.count(pii(tmpx,tmpy)))continue;
				insert(i,ma[pii(tmpx,tmpy)]);
			}
		}
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i])
			tarjan(i);
	for(int i=1;i<=n;++i){
		for(edge *j=pre[i];j;j=j->n){
			int e(j->e);
			if(bl[i]!=bl[e]){
				add(bl[i],bl[e]);
				++in[bl[e]];
//				cout<<i<<' '<<e<<
			}
		}
	}
	for(int i=1;i<=n;++i)
		++size[bl[i]];
	for(int i=1;i<=qlt;++i)
		if(!in[i])
			q.push(i),f[i]=size[i];
	while(!q.empty()){
		int k(q.front());
		q.pop();
		for(edge *i=adj[k];i;i=i->n){
			int e(i->e);
			--in[e];
			f[e]=max(f[e],f[k]+size[e]);
			if(!in[e])
				q.push(e);
		}
	}
	int ans(0);
	for(int i=1;i<=qlt;++i)
		ans=max(ans,f[i]);
	printf("%d",ans);
}