読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

codingame - Dwarfs standing on the shoulders of giants

メモ再帰によって簡単に解ける

template<typename T>
struct Edge
{
  int dst; T w;
  Edge() {};
  Edge(int dst): dst(dst) {w=1;};
  Edge(int dst, T w): dst(dst), w(w) {};
  bool operator < (const Edge &e){return w != e.w ? w > e.w : dst < e.dst;}
};

typedef vector<Edge<ll>> Edges;
typedef vector<Edges> Graph;

vector<bool> T;
vector<ll> U;

ll longest(int k, const Graph& g)
{
  if(T[k]) return U[k];
  for(auto e : g[k]) U[k] = max(U[k],e.w+longest(e.dst,g));
  T[k] = true;
  return U[k];
}

ll solve(const Graph &g)
{
  int n = g.size();
  T.resize(n);
  U.resize(n);
  fill(T.begin(),T.end(),false);
  fill(U.begin(),U.end(),0);
  REP(i,n) longest(i,g);
  return *max_element(U.begin(),U.end());
}

int main()
{
  int n; cin >> n;
  Graph g(10000);
  REP(i,n)
  {
    int s, t; cin >> s >> t;
    g[--s].push_back(Edge<ll>(--t));
  }
  cout << solve(g)+1 << endl;
  return 0;
}