注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

USACO[Holiday 2010 Bonus Competition/gold]cowpol  

2010-06-04 19:07:35|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

显然,对于一个党派,相距最远的两头牛中至少有一头是这个党派中深度最大的牛之一(这一点联系求树的直径,先随便从一点找最远,再从那儿找最远)。

所以每个党派的范围=max{最深的牛的深度+某头牛的深度-它们的最近公共祖先的深度*2,某头牛属于这个党派}。

问题的主要矛盾是LCA,然后,写了第一个Tarjan的LCA,由于数据太BT,要非递归,并且,即使这样下面的代码在Windows下无法编译(好像是因为开的内存太大了),但可以在USACO的测评系统下通过,所以在Linux下可以用的。

然后,LCA还有其它的算法可以做,有空再弄其它的,LCA这还是第一次写。

CODE:

/*

PROG: cowpol

LANG: C++

ID: boleyn.2

*/

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-6-4

DESCRIPTION:

TITLE: Cow Politics [Andre Kessler, 2009]

CONTENT:

Farmer John's cows are living on N (2 <= N <= 200,000) different

pastures conveniently numbered 1..N. Exactly N-1 bidirectional cow

paths (of unit length) connect these pastures in various ways, and

each pasture is reachable from any other cow pasture by traversing

one or more of these paths (thus, the pastures and paths form a

graph called a tree).

The input for a particular set of pastures will specify the parent

node P_i (0 <= P_i <= N) for each pasture. The root node will specify

parent P_i == 0, which means it has no parent.

The cows have organized K (1 <= K <= N/2) different political parties

conveniently numbered 1..K. Each cow identifies with a single

political party; cow i identifies with political party A_i (1 <=

A_i <= K). Each political party includes at least two cows.

The political parties are feuding and would like to know how much

'range' each party covers. The range of a party is the largest

distance between any two cows within that party (over cow paths).

For example, suppose political party 1 consists of cows 1, 3, and

6, political party 2 consists of cows 2, 4, and 5, and the pastures

are connected as follows (party 1 members are marked as -n-):

  -3-

   |

  -1-

 / | \

2  4  5

      |

     -6-

The greatest distance between any two pastures of political party

1 is 3 (between cows 3 and 6), and the greatest distance for political

party 2 is 2 (between cows 2 and 4, between cows 4 and 5, and between

cows 5 and 2).

Help the cows determine party ranges.

TIME LIMIT: 2 seconds

MEMORY LIMIT: 64MB

PROBLEM NAME: cowpol

INPUT FORMAT:

* Line 1: Two space-separated integers: N and K

* Lines 2..N+1: Line i+1 contains two space-separated integers: A_i

        and P_i

SAMPLE INPUT (file cowpol.in):

6 2

1 3

2 1

1 0

2 1

2 1

1 5

OUTPUT FORMAT:

* Lines 1..K: Line i contains a single integer that is the range of

        party i.

SAMPLE OUTPUT (file cowpol.out):

3

2

*/

#include <fstream>

using std::ifstream;

using std::ofstream;

using std::endl;

#include <list>

using std::list;

namespace sj

{

          template<unsigned int size>

          class UFSET

          {

                int p[size];

                int rank[size];

                public:

                void MAKE_SET()

                {

                     for (int i=0;i<size;rank[i++]=0) p[i]=i;

                }

                int FIND_SET(int x)

                {

                    if (p[x]==x) return x;

                    else return p[x]=FIND_SET(p[x]);

                }

                void UNION(int x,int y)

                {

                     x=FIND_SET(x);

                     y=FIND_SET(y);

                     if (x==y) return;

                     if (rank[x]<rank[y]) p[x]=y;

                     else

                     {

                        p[y]=x;

                        if (rank[x]==rank[y]) rank[x]++;

                     }

                }

          };

}

using namespace sj;

 

class Application

{

      ifstream cin;

      ofstream cout;

      static const int MAXN=200000;

      int N,K;

      int A[MAXN+1],P[MAXN+1];

      int size[MAXN+1];

      int root;

      list<int> child[MAXN+1];

      int deep[MAXN+1];

      int deepest[MAXN+1];

      list<int> question[MAXN+1];

      UFSET<MAXN+1> set;

      bool visited[MAXN+1];

      int ancestor[MAXN+1];

      int dfs(int node,int depth=1,int father=0)

      {

          deep[node]=depth;

          if (deep[deepest[A[node]]]<depth) deepest[A[node]]=node;

          question[A[node]].push_back(node);

          for (list<int>::iterator i=child[node].begin();

                                   i!=child[node].end();i++)

              if (*i!=father) dfs(*i,depth+1,node);

      }

      int LCA(int root)

      {

          static int depth;

          static int _node[MAXN+1];

          static int _father[MAXN+1];

          static list<int>::iterator _i[MAXN+1];

         

          _node[depth]=root;

          _father[depth]=0;

          _i[depth]=child[_node[depth]].begin();

          ancestor[_node[depth]]=_node[depth];

         

          for (;;)

          {

              int& node=_node[depth];

              int& father=_father[depth];

              list<int>::iterator& i=_i[depth];

             

              if (*i==father) i++;             

              if (i!=child[node].end())

              {

                 depth++;

                 _node[depth]=*i;

                 _father[depth]=node;

                 _i[depth]=child[_node[depth]].begin();

                 ancestor[_node[depth]]=_node[depth];

              }

              else

              {

                  visited[node]=true;

                  if (node==deepest[A[node]])

                  {

                     for (list<int>::iterator i=question[A[node]].begin();

                                              i!=question[A[node]].end();i++)

                         if (visited[*i])

                     {

                         int get=deep[node]+deep[*i]

                                 -deep[ancestor[set.FIND_SET(*i)]]*2;

                         if (size[A[node]]<get) size[A[node]]=get;

                     }

                  }

                  else if (visited[deepest[A[node]]])

                  {

                       int get=deep[node]+deep[deepest[A[node]]]

                               -deep[ancestor[set.FIND_SET(deepest[A[node]])]]*2;

                       if (size[A[node]]<get) size[A[node]]=get;

                  }

                  depth--;

                  if (depth<0) break;

                  set.UNION(_node[depth],*_i[depth]);

                  ancestor[set.FIND_SET(*_i[depth])]=_node[depth];

                  _i[depth]++;

              }

          }

      }

      /*

      int LCA(int node,int father=0)

      {

          ancestor[node]=node;

          for (list<int>::iterator i=child[node].begin();

                                   i!=child[node].end();i++)

              if (*i!=father)

              {

                 LCA(*i,node);

                 set.UNION(node,*i);

                 ancestor[set.FIND_SET(*i)]=node;

              }

          visited[node]=true;

         

          if (node==deepest[A[node]])

          {

             for (list<int>::iterator i=question[A[node]].begin();

                                      i!=question[A[node]].end();i++)

                 if (visited[*i])

                 {

                    int get=deep[node]+deep[*i]

                            -deep[ancestor[set.FIND_SET(*i)]]*2;

                    if (size[A[node]]<get) size[A[node]]=get;

                    //cout<<"LCA"<<node<<" "<<*i

                    //    <<"="<<ancestor[set.FIND_SET(*i)]<<endl;

                 }

          }

          else if (visited[deepest[A[node]]])

          {

               int get=deep[node]+deep[deepest[A[node]]]

                       -deep[ancestor[set.FIND_SET(deepest[A[node]])]]*2;

               if (size[A[node]]<get) size[A[node]]=get;

               //cout<<"LCA"<<node<<" "<<deepest[A[node]]

               //    <<"="<<ancestor[set.FIND_SET(deepest[A[node]])]<<endl;

          }

      }

      */

      public:

      Application(const char* input,const char* output)

                        :cin(input),cout(output)

      {

                        cin>>N>>K;

                        for (int i=1;i<=N;i++)

                            cin>>A[i]>>P[i];

      }

      ~Application()

      {

                    cin.close();

                    cout.close();

      }

      int run()

      {

          for (int i=1;i<=N;i++)

          {

              if (P[i]) child[P[i]].push_back(i);

              else root=i;

              child[i].push_back(P[i]);

          }

          dfs(root);

          set.MAKE_SET();

          LCA(root);

          for (int i=1;i<=K;i++)

              cout<<size[i]<<endl;

          return 0;

      }

};

 

int main()

{

    static

    Application app("cowpol.in","cowpol.out");

    return app.run();

}

 

  评论这张
 
阅读(653)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018