yeputons

Untitled

Jul 11th, 2012
107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <cassert>
  7. #include <algorithm>
  8. #include <string>
  9. #include <vector>
  10. #include <deque>
  11. #include <queue>
  12. #include <map>
  13. #include <set>
  14.  
  15. using namespace std;
  16.  
  17. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  18. #define pb push_back
  19. #define mp make_pair
  20. #define sz(x) ((int)(x).size())
  21.  
  22. typedef long long ll;
  23. typedef vector<ll> vll;
  24. typedef vector<int> vi;
  25. typedef vector<vi> vvi;
  26. typedef vector<bool> vb;
  27. typedef vector<vb> vvb;
  28. typedef pair<int, int> pii;
  29.  
  30. const int MAXN = 510;
  31. int ecnt;
  32.  
  33. bool can[MAXN][MAXN];
  34. int cans[MAXN][MAXN + 1];
  35.  
  36. int dyn[MAXN][MAXN][2];
  37.  
  38. int n;
  39. inline int modna(int x) {
  40. //  assert(0 <= x && x < 2 * n);
  41.   return x >= n ? x - n : x;
  42. }
  43. inline int modnm(int x) {
  44. //  assert(-n < x && x < n);
  45.   return x < 0 ? x + n : x;
  46. }
  47. /*inline int modn(int x) {
  48.   if (x < 0) x += n;
  49.   if (x >= n) x -= n;
  50.   assert(0 <= x && x < n);
  51.   return x;
  52. }*/
  53.  
  54. int dyn2[MAXN][MAXN][2];
  55. int dyn3[2][MAXN][MAXN];
  56.  
  57. int main() {
  58.   #ifdef DEBUG
  59.   freopen("std.in", "r", stdin);
  60.   freopen("std.out", "w", stdout);
  61.   #endif
  62.  
  63.   int type;
  64.   while (scanf("%d%d", &n, &type) >= 1) {
  65.     memset(can, 0, sizeof can);
  66.     for (int i = 0; i < n; i++) {
  67.       for (int pos = 0;; pos++) {
  68.         int x;
  69.         scanf("%d", &x);
  70.         cans[i][pos] = x - 1;
  71.         if (!x) break;
  72.  
  73.         x--;
  74.         can[i][x] = true;
  75.       }
  76.     }
  77.     memset(dyn, 0, sizeof dyn);
  78.  
  79.     for (int len = 2; len <= n; len++)
  80.       for (int st = 0; st < n; st++) {
  81.         {// 0
  82.           int en = modna(st + len - 1);
  83.           for (int ne = modna(st + 1);; ne = modna(ne + 1)) {
  84.             if (can[st][ne])
  85.               dyn[en][st][0] = max(dyn[en][st][0], 1 + max(dyn[en][ne][0], dyn[modna(st + 1)][ne][1]));
  86.             if (ne == en) break;
  87.           }
  88.         }
  89.         {// 1
  90.           int en = modnm(st - len + 1);
  91.           for (int ne = modnm(st - 1);; ne = modnm(ne - 1)) {
  92.             if (can[st][ne])
  93.               dyn[en][st][1] = max(dyn[en][st][1], 1 + max(dyn[en][ne][1], dyn[modnm(st - 1)][ne][0]));
  94.             if (ne == en) break;
  95.           }
  96.         }
  97.       }
  98.     pii ans(-1, -1);
  99.     for (int st = 0; st < n; st++) {
  100.       int en = modnm(st - 1);
  101.       ans = max(ans, mp(dyn[en][st][0], st));
  102.     }
  103.  
  104.     if (type) {
  105. //      eprintf("%d\n", clock());
  106.       memset(dyn3, 0x80, sizeof dyn3);
  107.       for (int i = 0; i < n; i++) dyn3[0][i][i] = dyn3[1][i][i] = 0;
  108.       for (int len = 2; len <= n; len++)
  109.         for (int st = 0; st < n; st++) { // 0
  110.           int en = modna(st + len - 1);
  111.           for (int ne = modna(st + 1);; ne = modna(ne + 1)) {
  112.             if (can[st][ne])
  113.               dyn3[0][st][en] = max(dyn3[0][st][en], 1 + dyn3[0][ne][en]);
  114.             if (ne == en) break;
  115.           }
  116.         }
  117.       for (int len = 2; len <= n; len++)
  118.         for (int st = 0; st < n; st++) { // 1
  119.           int en = modnm(st - len + 1);
  120.           for (int ne = modnm(st - 1);; ne = modnm(ne - 1)) {
  121.             if (can[st][ne])
  122.               dyn3[1][st][en] = max(dyn3[1][st][en], 1 + dyn3[1][ne][en]);
  123.             if (ne == en) break;
  124.           }
  125.         }
  126. //      eprintf("%d\n", clock());
  127.      
  128.       memset(dyn2, 0, sizeof dyn2);
  129.       for (int c = 0; c < n; c++) {
  130.         for (int i = 0; i < n; i++)
  131.           dyn2[i][i][0] = dyn2[i][i][1] = !!can[c][i];
  132.  
  133.         for (int en = 0; en < n; en++) {
  134.           // 0
  135.           for (int st = modnm(en - 1); st != en; st = modnm(st - 1)) {
  136.             int &val = dyn2[st][en][0] = dyn2[modna(st + 1)][en][0];
  137.             if (can[c][st])
  138.               val = max(val, 1 + dyn[en][st][0]);
  139.           }
  140.           // 1
  141.           for (int st = modna(en + 1); st != en; st = modna(st + 1)) {
  142.             int &val = dyn2[st][en][1] = dyn2[modnm(st - 1)][en][1];
  143.             if (can[c][st])
  144.               val = max(val, 1 + dyn[en][st][1]);
  145.           }
  146.         }
  147.  
  148.         for (int a = 0; a < n; a++) if (a != c)
  149.         for (int i = 0; cans[a][i] >= 0; i++) {
  150.           int b = cans[a][i];
  151.           if (b == c) continue;
  152.           int dir = ((a > b) + (a > c) + (b > c)) & 1;
  153.  
  154.           int cans = 1;
  155.           cans += dyn3[dir][b][c];
  156.  
  157.           if (dir == 0) {
  158.             int st = modna(a + 1);
  159.             if (st != b) {
  160.               int en = modnm(b - 1);
  161.               cans += max(dyn2[st][en][0], dyn2[en][st][1]);
  162.             }
  163.           } else {
  164.             int st = modnm(a - 1);
  165.             if (st != b) {
  166.               int en = modna(b + 1);
  167.               cans += max(dyn2[st][en][1], dyn2[en][st][0]);
  168.             }
  169.           }
  170.           if (cans > ans.first) {
  171.             ans.first = cans;
  172.             ans.second = a;
  173.           }
  174.         }
  175.       }
  176. //      eprintf("%d\n", clock());
  177.     }
  178.     #ifdef DEBUG
  179.     printf("%d\n", ans.first);
  180.     #else
  181.     printf("%d\n%d\n", ans.first, ans.second + 1);
  182.     #endif
  183.   }
  184.   #ifdef DEBUG
  185.   eprintf("time=%d\n", clock());
  186.   #endif
  187.   return 0;
  188. }
RAW Paste Data