Advertisement
libobil

Untitled

Mar 29th, 2023
640
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.96 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <numeric>
  4. #include <vector>
  5. #include <bitset>
  6. #include <cmath>
  7.  
  8. typedef long long llong;
  9. const int MAXN = 5000 + 10;
  10. const int INF  = 1e9;
  11.  
  12. const int BUFF_SIZE = 1e5;
  13. int buffPos = BUFF_SIZE - 1;
  14. char buff[BUFF_SIZE];
  15.  
  16. inline void readChar()
  17. {
  18.     if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
  19. }
  20.  
  21. inline void readString(char s[])
  22. {
  23.     int pos = 0;
  24.     for (; buff[buffPos] < '0' || buff[buffPos] > '1'; readChar());
  25.     for (; buff[buffPos] >= '0' && buff[buffPos] <= '1'; readChar())
  26.         s[pos++] = buff[buffPos];
  27. }
  28.  
  29. inline void readInt(int &num)
  30. {
  31.     num = 0;
  32.     for (; buff[buffPos] < '0' || buff[buffPos] > '9'; readChar());
  33.     for (; buff[buffPos] >= '0' && buff[buffPos] <= '9'; readChar())
  34.         num = 10 * num + buff[buffPos] - '0';
  35. }
  36.  
  37. int n, m;
  38. int g[MAXN];
  39. int perm[MAXN];
  40. int common[MAXN][MAXN];
  41. std::vector <int> v[MAXN];
  42. std::bitset <MAXN> bs[MAXN];
  43. std::bitset <MAXN> neighBS[MAXN];
  44. std::bitset <MAXN> neighNeighBS[MAXN];
  45. std::bitset <MAXN> pairs[MAXN];
  46. std::bitset <MAXN> neigh;
  47. std::bitset <MAXN> vis;
  48. void solve()
  49. {
  50.     if (m > n * sqrt(n))
  51.     {
  52.         std::cout << 2 << '\n';
  53.         return;
  54.     }
  55.  
  56.     for (int i = 1 ; i <= n ; ++i)
  57.     {
  58.         vis.reset();
  59.         for (const int &j : v[i])
  60.         {
  61.             for (const int &k : v[j])
  62.             {
  63.                 if (i == k) continue;
  64.                 if (vis[k])
  65.                 {
  66.                     std::cout << 2 << '\n';
  67.                     return;
  68.                 }
  69.  
  70.                 vis[k] = 1;
  71.                 common[i][k] = j;
  72.                 pairs[i][k] = 1;
  73.             }
  74.         }
  75.     }
  76.  
  77.     for (int i = 1 ; i <= n ; ++i)
  78.     {
  79.         for (const int &j : v[i])
  80.         {
  81.             neighBS[i] |= bs[j];
  82.         }
  83.     }
  84.  
  85.     for (int i = 1 ; i <= n ; ++i)
  86.     {
  87.         for (const int &j : v[i])
  88.         {
  89.             neighNeighBS[i] |= neighBS[j];
  90.         }
  91.  
  92.         neighNeighBS[i][i] = 0;
  93.     }
  94.  
  95.     for (int i = 1 ; i <= n ; ++i)
  96.     {
  97.         for (int k = 1 ; k <= n ; ++k)
  98.         {
  99.             if (pairs[i][k] && bs[i][k] && g[common[i][k]] > 2)
  100.             {
  101.                 std::cout << 3 << '\n';
  102.                 return;
  103.             }
  104.         }
  105.     }
  106.  
  107.     for (int i = 1 ; i <= n ; ++i)
  108.     {
  109.         for (int k = i + 1 ; k <= n ; ++k)
  110.         {
  111.             if (!pairs[i][k] || bs[i][k]) continue;
  112.             if (neighNeighBS[i][k])
  113.             {
  114.                 std::cout << 3 << '\n';
  115.                 return;
  116.             }
  117.         }
  118.     }
  119.  
  120.     for (int i = 1 ; i <= n ; ++i)
  121.     {
  122.         if (g[i] == 1) continue;
  123.         for (const int &j : v[i])
  124.         {
  125.             if (g[i] >= 3 && g[j] >= 2)
  126.             {
  127.                 std::cout << 4 << '\n';
  128.                 return;
  129.             }
  130.  
  131.             if (g[i] == 2 && g[j] == 2)
  132.             {
  133.                 int curr = v[i][0];
  134.                 if (curr == j) curr = v[i][1];
  135.                 int curr2 = v[j][0];
  136.                 if (curr2 == i) curr2 = v[j][1];
  137.                 if (curr != curr2)
  138.                 {
  139.                     std::cout << 4 << '\n';
  140.                     return;
  141.                 }
  142.             }
  143.         }
  144.     }
  145.  
  146.     std::cout << -1 << '\n';
  147. }
  148.  
  149. char s[MAXN];
  150. void input()
  151. {
  152.     readInt(n);
  153.     for (int i = 1 ; i < n ; ++i)
  154.     {
  155.         readString(s);
  156.         for (int j = i + 1 ; j <= n ; ++j)
  157.         {
  158.             bs[i][j] = s[j - i - 1] - '0';
  159.             bs[j][i] = s[j - i - 1] - '0';
  160.             if (s[j - i - 1] == '1')
  161.             {
  162.                 g[i]++; g[j]++;
  163.                 v[i].push_back(j);
  164.                 v[j].push_back(i);
  165.                 m++;
  166.             }
  167.         }
  168.     }
  169. }
  170.  
  171. void fastIO()
  172. {
  173.     std::ios_base :: sync_with_stdio(0);
  174.     std::cout.tie(nullptr);
  175.     std::cin.tie(nullptr);
  176. }
  177.  
  178. int main()
  179. {
  180.     srand(229295);
  181.     fastIO();
  182.     input();
  183.     solve();
  184.  
  185.     return 0;
  186. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement