```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<set>
using namespace std;
const int N=1e5+10;
const int M=1e6+100;
struct EDGE{
int v,nxt;
}ed[M<<1],edge[M<<1];
int n,r,c,x[N],y[N],z[N],hd[N],e0,e,head[N];
void ade(int u,int v){
ed[++e0].v=v; ed[e0].nxt=hd[u]; hd[u]=e0;
}
void adde(int u,int v){
edge[++e].v=v; edge[e].nxt=head[u]; head[u]=e;
}
int dfn[N],low[N],cnt,cnt2,col[N],val[N];
bool ins[N];
stack<int> st;
void Tarjan(int x){
dfn[x]=low[x]=++cnt;
st.push(x); ins[x]=1;
for(int i=hd[x];i;i=ed[i].nxt){
int v=ed[i].v;
if(!dfn[v])
Tarjan(v),low[x]=min(low[x],low[v]);
else if(ins[v])
low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x]){
++cnt2;
int tp=st.top();
while(tp!=x){
st.pop();
col[tp]=cnt2;
++val[cnt2];
ins[tp]=0;
tp=st.top();
}
st.pop();
col[tp]=cnt2;
++val[cnt2];
ins[tp]=0;
}
}
int in[N],f[N];
queue<int> q;
int topodp(){
for(int i=1;i<=cnt2;i++)
if(!in[i]) q.push(i),f[i]=val[i];
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=edge[i].nxt){
int v=edge[i].v;
f[v]=max(f[v],f[x]+val[v]);
if(!(--in[v])) q.push(v);
}
}
int ans=0;
for(int i=1;i<=cnt2;i++)
ans=max(ans,f[i]);
return ans;
}
typedef long long ll;
struct NODE{
ll site; int idx;
NODE(){}
NODE(ll _site,int _idx) : site(_site) , idx(_idx) {}
bool operator <(const NODE rhs) const
{
return site<rhs.site;
}
};
vector<int> row[N],line[N];
set<NODE> s;
const ll p=1e6;
const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={-1,0,1,-1,1,-1,0,1};
inline ll calc(int x,int y){
return 1ll*x+p*y;
}
int main(){
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
scanf("%d%d%d",&n,&r,&c);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&x[i],&y[i],&z[i]),row[x[i]].push_back(i),
line[y[i]].push_back(i),s.insert(NODE(calc(x[i],y[i]),i));
for(int i=1;i<=n;i++)
switch(z[i]){
case 1:{
for(int j=0;j<row[x[i]].size();j++)
if(row[x[i]][j]!=i) ade(i,row[x[i]][j]);
break;
}
case 2:{
for(int j=0;j<line[y[i]].size();j++)
if(line[y[i]][j]!=i) ade(i,line[y[i]][j]);
break;
}
case 3:{
for(int j=0;j<8;j++){
auto it=s.find(NODE(calc(x[i]+dx[j],y[i]+dy[j]),0));
if(it!=s.end()) ade(i,it->idx);
}
break;
}
}
for(int i=1;i<=n;i++)
if(!dfn[i]) Tarjan(i);
// for(int i=1;i<=n;i++)
// printf("%d %d\n",dfn[i],col[i]);
// for(int i=1;i<=cnt2;i++)
// printf("%d\n",val[i]);
for(int x=1;x<=n;x++)
for(int i=hd[x];i;i=ed[i].nxt){
int v=ed[i].v;
if(col[x]!=col[v])
adde(col[x],col[v]),++in[col[v]];
}
printf("%d\n",topodp());
return 0;
}
```
by Focus_on @ 2022-10-27 20:25:09
我第九个点Wa，开O2后AC。。。
不是很理解
by I_Flipped @ 2022-11-09 12:16:29