开小RE开大MLE,50pts一只过不去,玄赏RP+=100
查看原帖
开小RE开大MLE,50pts一只过不去,玄赏RP+=100
473401
zcxnb楼主2024/11/3 11:17
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5;
int n,r,c,tot,l,colnum,ans;
int xx[N],yy[N],t[N],dfn[N],vis[N],low[N],s[N],num[N],col[N],ru[N],dp[N];
int nx[8]={-1,-1,-1,0,1,1,1,0},ny[8]={-1,0,1,1,1,0,-1,-1};
vector<int>b[N],newb[N];
map<int,map<int,int> >mp,pan;
queue<int>q;
void tarjan(int x){
	dfn[x]=low[x]=++tot;
	s[++l]=x;
	vis[x]=1;
	for(int i:b[x]){
		if(!dfn[i])  tarjan(i);
		if(vis[i])  low[x]=min(low[i],low[x]);
	}
	if(low[x]==dfn[x]){
		colnum++;
		while(s[l]!=x){
			col[s[l]]=colnum;
			if(s[l]>r+c)  num[colnum]++;
			vis[s[l]]=0;
			l--;
		}
		col[s[l]]=colnum;
		if(s[l]>r+c)  num[colnum]++;
		vis[s[l]]=0;
		l--;
	}
}
int main(){
	scanf("%d%d%d",&n,&r,&c);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&xx[i],&yy[i],&t[i]);
		b[xx[i]].push_back(r+c+i);
		b[yy[i]+r].push_back(r+c+i);
		if(t[i]==1)  b[r+c+i].push_back(xx[i]);
		if(t[i]==2)  b[r+c+i].push_back(yy[i]+r);
		mp[xx[i]][yy[i]]=i;
	}
	for(int i=1;i<=n;i++){
		if(t[i]==3){
			for(int j=0;j<8;j++){
				int mx=xx[i]+nx[j],my=yy[i]+ny[j];
				if(mx<1||my<1||mx>r||my>c)  continue;
				if(mp[mx][my])  b[r+c+i].push_back(r+c+mp[mx][my]);
			}
		}
	}
	for(int i=1;i<=r+c+n;i++){
		if(!dfn[i])  tarjan(i);
	}
	for(int i=1;i<=r+c+n;i++){
		for(int j:b[i]){
			if(col[i]!=col[j]){
				pan[col[i]][col[j]]=1;
			}
		}
	}
	for(int i=1;i<=r+c+n;i++){
		for(int j:b[i]){
			if(pan[col[i]][col[j]]){
				newb[col[i]].push_back(col[j]);
				pan[col[i]][col[j]]=0;
				ru[col[j]]++;
			}
		}
	}
	for(int i=1;i<=colnum;i++){
		if(!ru[i])  q.push(i),dp[i]=num[i];
	}
	while(!q.empty()){
		int k=q.front();
		q.pop();
		for(int i:newb[k]){
			ru[i]--;
			if(!ru[i])  q.push(i);
			dp[i]=max(dp[i],dp[k]+num[i]);
		}
	}
	for(int i=1;i<=colnum;i++){
		ans=max(ans,dp[i]);
	}
	printf("%d",ans);
}
2024/11/3 11:17
加载中...