记录编号	459140	评测结果	AAAAAAAAAA
题目名称	[SDOI 2010] 所驼门王的宝藏	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.633 s
提交时间	2017-10-12 19:11:58	内存使用	104.17 MiB

# pragma GCC optimize("O3")
# include "iostream"
# include "stdio.h"
# include "algorithm"
# include "cmath"
# include "string.h"
# include "vector"
# define maxn 100005
using namespace std;
int n,r,c,sum,ans;
vector<int> vex[1000005];
vector<int> vey[1000005];
struct map{int x,y,dor;}e[maxn];
int st[maxn],zz;
struct node{int fro,to,next;}e1[maxn*40];
void add(int x,int y){
     e1[++zz].fro=x;
     e1[zz].to=y;
     e1[zz].next=st[x];
     st[x]=zz;
}
int low[maxn],dfn[maxn],tim,cnt,bl[maxn],size[maxn];
int sta[maxn],top;
bool vis[maxn];
void tarjan(int x){
     low[x]=dfn[x]=++tim;
     sta[++top]=x;
     vis[x]=1;
     for(int i=st[x];i;i=e1[i].next){
         int t=e1[i].to;
         if(!dfn[t]){
            tarjan(t);
            low[x]=min(low[x],low[t]);
         }else if(vis[t]) low[x]=min(low[x],dfn[t]);
     }
     if(dfn[x]==low[x]){
        cnt++;int k;
        while(true){
              k=sta[top--];
              bl[k]=cnt;
              size[cnt]++;
              vis[k]=0;
              if(k==x) break;
        }
     }
}
int zz1,st2[maxn],ru[maxn],f[maxn];
struct nodee{int to,next;}e2[maxn*40];
void addd(int x,int y){
     e2[++zz1].next=st2[x];
     e2[zz1].to=y;
     st2[x]=zz1;
}
void dfs(int x){
     if(f[x]) return;
     for(int i=st2[x];i;i=e2[i].next)
         {dfs(e2[i].to);f[x]=max(f[x],f[e2[i].to]);}
     f[x]+=size[x];
}
int main(){
	freopen("sdoi10sotomon.in","r",stdin);
	freopen("sdoi10sotomon.out","w",stdout);
    scanf("%d%d%d",&n,&r,&c);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].dor);
        vex[e[i].x].push_back(i);
        vey[e[i].y].push_back(i);
    }
    for(int i=1;i<=n;i++){
        if(e[i].dor==1){
           int sz=vex[e[i].x].size();
           for(int j=0;j<sz;j++){
               int t=vex[e[i].x][j];
               if(t==i) continue; 
               add(i,t);
           }continue;
        }
        if(e[i].dor==2){
           int sz=vey[e[i].y].size();
           for(int j=0;j<sz;j++){
               int t=vey[e[i].y][j];
               if(t==i) continue; 
               add(i,t);
           }continue;
        }
        if(e[i].dor==3){
           int sz=vex[e[i].x-1].size();
           for(int j=0;j<sz;j++){
               int t=vex[e[i].x-1][j];
               if(e[t].y==e[i].y||e[t].y==e[i].y+1||e[t].y==e[i].y-1) 
                  add(i,t);
           }
            
           sz=vex[e[i].x+1].size();
           for(int j=0;j<sz;j++){
               int t=vex[e[i].x+1][j];
               if(e[t].y==e[i].y||e[t].y==e[i].y+1||e[t].y==e[i].y-1) 
                  add(i,t);
           }
            
           sz=vey[e[i].y-1].size();
           for(int j=0;j<sz;j++){
               int t=vey[e[i].y-1][j];
               if(e[t].x-e[i].x==0) {add(i,t);break;}
           }
           sz=vey[e[i].y+1].size();
           for(int j=0;j<sz;j++){
               int t=vey[e[i].y+1][j];
               if(e[t].x-e[i].x==0) {add(i,t);break;}
           }
        }
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=zz;i++){
        if(bl[e1[i].fro]!=bl[e1[i].to]){
           addd(bl[e1[i].fro],bl[e1[i].to]);
           ru[bl[e1[i].to]]++;
        }
    }
    for(int i=1;i<=cnt;i++)
        if(!ru[i]){
          dfs(i);
          ans=max(ans,f[i]);
        }
    printf("%d",ans);
}