记录编号	594779	评测结果	AAAAAAAAAA
题目名称	宝藏	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	2.018 s
提交时间	2024-10-05 09:18:30	内存使用	48.62 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define	MAXN 1000010 
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct node{
	int x,y,w,id;
}pnt[MAXN*2];
int ad_x[10]={0,1,1,1,0,0,-1,-1,-1},ad_y[10]={0,1,0,-1,1,-1,1,0,-1};
int R,C,n,idx,cnt,scc,top,ans;
int hd[MAXN*3],ed[MAXN],nxt[MAXN],beg[MAXN];
int val[MAXN*3],dfn[MAXN*3],bel[MAXN*3],ins[MAXN*3],low[MAXN*3];
int stk[MAXN];
vector <int> vec[MAXN];
int siz[MAXN],dp[MAXN],ind[MAXN];
std::map <pair<int,int> , int> mp,p;
queue <int> q;
void build(int x,int y){
	nxt[++idx]=hd[x];
	ed[idx]=y;
	hd[x]=idx;
	beg[idx]=x;
}
void clear(int now){
	int y=-1;
	scc++;
//	cout<<scc<<" ";
	while(y!=now){
		y=stk[top--];
		siz[scc]+=val[y];
		bel[y]=scc;
		ins[y]=0;
//		cout<<y<<" ";
	}
//	cout<<"siz: "<<siz[scc]<<endl;
}
void Tarjan(int now){
	dfn[now]=++cnt,low[now]=cnt;
	stk[++top]=now,ins[now]=1;
	for(int i=hd[now];i;i=nxt[i]){
		int y=ed[i];
		if(!dfn[y]){
			Tarjan(y);
			low[now]=min(low[now],low[y]);
		}else if(ins[y])low[now]=min(dfn[y],low[now]);
	}
	if(dfn[now]==low[now])clear(now);
}
int main(){
	freopen("hzsotomon.in","r",stdin);
	freopen("hzsotomon.out","w",stdout);
	n=read(),R=read(),C=read();
	for(int i=1;i<=n;i++){
		pnt[i].x=read(),pnt[i].y=read(),pnt[i].w=read(),pnt[i].id=i;
		mp[make_pair(pnt[i].x,pnt[i].y)]=i;
	}
	for(int i=1;i<=n;i++){
		if(pnt[i].w==1){
			val[pnt[i].x]++;
			build(pnt[i].y+R,pnt[i].x);
		}else if(pnt[i].w==2){
			val[pnt[i].y+R]++;
			build(pnt[i].x,pnt[i].y+R);
		}else{
			val[R+C+i]++;
			build(pnt[i].x,R+C+i);
			build(pnt[i].y+R,R+C+i);
			for(int j=1;j<=8;j++){
				pair <int,int>s=make_pair(pnt[i].x+ad_x[j],pnt[i].y+ad_y[j]);
				int id=mp[s];
				if(!id)continue;
				if(pnt[id].w==1){
					build(R+C+i,pnt[id].x);	
				}else if(pnt[id].w==2){
					build(R+C+i,pnt[id].y+R);
				}else{
					build(R+C+i,R+C+id);
				}
			}
		}
	}
	for(int i=1;i<=n+R+C;i++){
		if(!bel[i]&&val[i]){
			Tarjan(i);
		}
	}
	for(int i=1;i<=idx;i++){
		int x=beg[i],y=ed[i];
		pair <int,int> s=make_pair(x,y);
		if(bel[x]!=bel[y]&&!mp[s]&&bel[x]&&bel[y]){
			ind[bel[y]]++;
			vec[bel[x]].push_back(bel[y]);
			mp[s]=1;
		}
	}
	for(int i=1;i<=scc;i++){
		if(!ind[i])q.push(i);
		dp[i]=siz[i];
	}
//	for(int i=1;i<=R+C+n;i++)cout<<i<<" "<<val[i]<<endl;
	while(!q.empty()){
		int fnt=q.front();
		ans=max(ans,dp[fnt]);
		q.pop();
		for(int i=0;i<vec[fnt].size();i++){
			int y=vec[fnt][i];
			dp[y]=max(dp[y],dp[fnt]+siz[y]);
			ind[y]--;
//			cout<<fnt<<" "<<y<<" "<<dp[fnt]<<" "<<dp[y]<<endl;
			if(!ind[y])q.push(y);
		}
	}
	cout<<ans;
	return 0;
}