记录编号	594752	评测结果	AAAAAAAAAA
题目名称	宝藏	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.798 s
提交时间	2024-10-04 21:09:35	内存使用	32.68 MiB

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0,z=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')z=-1;ch=getchar();} 
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar(); }
	return x*z;
}
const int N=1e5+5,M=1e6+5,T=2e6+5e5;
const int dx[8]={1,1,1,0,0,-1,-1,-1};
const int dy[8]={1,0,-1,1,-1,1,0,-1};
int t,n,m,num;
int h1[T],ne1[M],e1[M],idx1;
int h2[T],ne2[M],e2[M],idx2;
int edu[M],edv[M],ced;
int stk[T],top,dfn[T],low[T],tim;
bool ins[T];
int scc[T],val[T],cnt;
int f[T],in[T];
struct node{
	int x,y,t;
	bool operator < (const node &t) const{
		if(x!=t.x) return x<t.x;
		return y<t.y;
	}
}a[N];
void add1(int a,int b){
	edu[++ced]=a,edv[ced]=b;
	e1[++idx1]=b,ne1[idx1]=h1[a],h1[a]=idx1;
} 
void add2(int a,int b){
	e2[++idx2]=b,ne2[idx2]=h2[a],h2[a]=idx2;
}
int get(int x,int y){
	int l=1,r=t;
	while(l<=r){
		int mid=l+r>>1;
		if(a[mid].x==x&&a[mid].y==y) return mid;
		else if(a[mid].x<x||(a[mid].x==x&&a[mid].y<y)) l=mid+1;
		else r=mid-1;
	}
	return -1;
}
void tarjan(int u){
	low[u]=dfn[u]=++tim;
	ins[u]=1,stk[++top]=u;
	for(int i=h1[u];i;i=ne1[i]){
		int v=e1[i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		scc[u]=++cnt,val[cnt]=u>n+m;
		while(stk[top]!=u){
			scc[stk[top]]=cnt;
			val[cnt]+=(stk[top]>n+m);
			ins[stk[top--]]=0;
		}
		ins[stk[top--]]=0;
	} 
}
int main(){
	freopen("hzsotomon.in","r",stdin);
	freopen("hzsotomon.out","w",stdout);
	t=read(),n=read(),m=read();
	for(int i=1;i<=t;++i) a[i].x=read(),a[i].y=read(),a[i].t=read();
	sort(a+1,a+1+t);
	for(int i=1;i<=t;++i){
		add1(a[i].x,n+m+i);
		add1(a[i].y+n,n+m+i);
		if(a[i].t==1) add1(n+m+i,a[i].x);
		else if(a[i].t==2) add1(n+m+i,a[i].y+n);
		else{
			for(int j=0;j<8;++j){
				int x=a[i].x+dx[j],y=a[i].y+dy[j];
				if(x>=1&&x<=n&&y>=1&&y<=m){
					int id=get(x,y);
					if(id!=-1) add1(n+m+i,n+m+id);
				}
			}
		}
	}
	num=n+m+t;
	for(int i=1;i<=num;++i)
		if(!dfn[i]) tarjan(i);
	for(int i=1;i<=ced;++i){
		if(scc[edu[i]]!=scc[edv[i]]){
			add2(scc[edu[i]],scc[edv[i]]);
			++in[scc[edv[i]]];
		}
	}
	queue<int> q;
	for(int i=1;i<=cnt;++i)
		if(!in[i]){
			q.push(i);
			f[i]=val[i];
		}
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=h2[u];i;i=ne2[i]){
			int v=e2[i];
			f[v]=max(f[v],f[u]+val[v]);
			if(--in[v]==0) q.push(v);
		}
	}
	int ans=0;
	for(int i=1;i<=cnt;++i)
		ans=max(ans,f[i]);
	printf("%d\n",ans);
	return 0; 
}