daily pastebin goal
30%
SHARE
TWEET

Untitled

a guest Aug 30th, 2014 2,243 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. const int NMAX = 1010;
  8.  
  9. int N, K, V[10][NMAX], Pos[10][NMAX], Best[NMAX], Ans;
  10. vector<int> G[NMAX];
  11. bool Used[NMAX];
  12.  
  13. void DFS(int Node)
  14. {
  15.     Used[Node] = 1;
  16.     for(int i = 0; i < G[Node].size(); ++ i)
  17.     {
  18.         if(!Used[G[Node][i]])
  19.             DFS(G[Node][i]);
  20.         Best[Node] = max(Best[Node], Best[ G[Node][i] ] + 1);
  21.     }
  22.     Best[Node] = max(Best[Node], 1);
  23.     Ans = max(Ans, Best[Node]);
  24. }
  25.  
  26. int main()
  27. {
  28.    // freopen("d.in", "r", stdin);
  29.    // freopen("d.out", "w", stdout);
  30.  
  31.     scanf("%i %i", &N, &K);
  32.     for(int i = 1; i <= K; ++ i)
  33.         for(int j = 1; j <= N; ++ j)
  34.         {
  35.             scanf("%i", &V[i][j]);
  36.             Pos[i][ V[i][j] ] = j;
  37.         }
  38.  
  39.     for(int i = 1; i <= N; ++ i)
  40.         for(int j = 1; j <= N; ++ j)
  41.         {
  42.             if(i == j) continue;
  43.             bool OK = 1;
  44.             for(int k = 1; k <= K; ++ k)
  45.                 if(Pos[k][i] >= Pos[k][j])
  46.                     OK = 0;
  47.             if(OK) G[i].push_back(j);
  48.         }
  49.  
  50.     for(int i = 1; i <= N; ++ i)
  51.         if(!Used[i])
  52.             DFS(i);
  53.  
  54.     printf("%i\n", Ans);
  55. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top