记录编号	313669	评测结果	AAAAAAAAAA
题目名称	宝藏	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	0.953 s
提交时间	2016-10-01 19:06:56	内存使用	122.22 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stack>


using namespace std;

typedef long long LL;

stack<int> q;             

const int maxn=100000+100;

const int mv[8][2]={{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1}};

int T,N,M,len1,len2,tim=0,cnt=0;

int head1[maxn],f[maxn],head2[maxn],dfn[maxn],low[maxn],belong[maxn],data[maxn];
        
bool flag[maxn];
                             
LL get(int i,int j)
{
    return ((LL)i-1)*(LL)N+(LL)j;
}

struct node
{
    int x,y,type;
    LL num;
    int pos;   
}A[maxn],B[maxn];

struct edge
{int to,next;
}e1[maxn*100],e2[maxn*50];

void ADD1(int x,int y)
{len1++;e1[len1].to=y,e1[len1].next=head1[x];head1[x]=len1;}

void ADD2(int x,int y)
{len2++;e2[len2].to=y,e2[len2].next=head2[x];head2[x]=len2;}

bool compnum(node a,node b)
{
     return a.num<b.num;
};

void tar(int x)
{
     //printf(" %d\n",x);
     //puts("OK");
     dfn[x]=low[x]=++tim;
     q.push(x);flag[x]=1;
     for(int t,i=head1[x];i;i=e1[i].next)
     {
      t=e1[i].to;
      if(!dfn[t])
      {
                 tar(t);
                 low[x]=min(low[x],low[t]);         
      }
      else if(flag[t])
      {
           low[x]=min(low[x],dfn[t]);
      }
     }
     if(low[x]==dfn[x])
      {
               cnt++;
               while(q.top()!=x)
               {
                  belong[q.top()]=cnt;
                  data[cnt]++;
                  flag[q.top()]=0;
                  q.pop();
               }
                  belong[q.top()]=cnt;
                  data[cnt]++;
                  flag[q.top()]=0;
                  q.pop();
               //puts("OK");
                /*flag[q.top()]=0;
                belong[q.top()]=cnt;
                data[cnt]++;
                q.pop();*/   
      }
}

int dp(int x)
{
    
    if(f[x])return f[x];
    f[x]=data[x];
    for(int t,i=head2[x];i;i=e2[i].next)
    {
            t=e2[i].to;
            f[x]=max(f[x],data[x]+dp(t));
    }
    return f[x];
}

int main()
{
    freopen("sdoi10sotomon.in","r",stdin);
    freopen("sdoi10sotomon.out","w",stdout);
    scanf("%d%d%d",&T,&N,&M);
    for(int i=1;i<=T;i++)
    {
     scanf("%d%d%d",&A[i].x,&A[i].y,&A[i].type);
     B[i].x=A[i].x,B[i].y=A[i].y,B[i].type=A[i].type;
     A[i].num=get(A[i].x,A[i].y);
     B[i].num=get(A[i].y,A[i].x);
     A[i].pos=B[i].pos=i;
     
    }     
    sort(A+1,A+T+1,compnum);
    sort(B+1,B+T+1,compnum);
    for(int i=1;i<=T;i++)
    {
            if(A[i].type==1)
            {
             int ha=i-1;
             while(A[ha].x==A[i].x&&ha)
             {ADD1(A[i].pos,A[ha].pos);ha--;}
             ha=i+1;
             while(A[ha].x==A[i].x&&ha<=T)
             {ADD1(A[i].pos,A[ha].pos);ha++;}
            }       
            if(B[i].type==2)
            {
             int ha=i-1;
             while(B[ha].y==B[i].y&&ha)
             {ADD1(B[i].pos,B[ha].pos);ha--;}
             ha=i+1;
             while(B[ha].y==B[i].y&&ha<=T)
             {ADD1(B[i].pos,B[ha].pos);ha++;}              
            }
            if(A[i].type==3)
            {
                for(int xx,yy,j=0;j<8;j++)
                {
                 xx=A[i].x+mv[j][0],yy=A[i].y+mv[j][1];
                 LL haha=get(xx,yy);
                 if(xx>0&&xx<=N&&yy>0&&yy<=M)
                 {
                 int l=1,r=T;
                 while(l<=r)
                 {
                    int mid=(l+r)>>1;
                    if(A[mid].num<haha)
                    l=mid+1;
                    else r=mid-1;        
                 }
                 if(A[l].num==haha)
                 ADD1(A[i].pos,A[l].pos);
                 }
                }  
            }                                   
    }         
    for(int i=1;i<=T;i++)if(!dfn[i])tar(i);
    for(int ha=1;ha<=T;ha++)
    {
           for(int t,i=head1[ha];i;i=e1[i].next)
           {
             t=e1[i].to;
             if(belong[t]!=belong[ha])
             ADD2(belong[ha],belong[t]);      
           } 
    }  
    //puts("OK");
    //printf("++ %d\n",cnt);
    int Ans=0;
    for(int i=1;i<=cnt;i++)
    {Ans=max(Ans,dp(i));}
     printf("%d",Ans);
     
     fclose(stdin);
     fclose(stdout);                                     
    return 0;
}