Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <numeric>
- #include <vector>
- #include <bitset>
- #include <cmath>
- typedef long long llong;
- const int MAXN = 5000 + 10;
- const int INF = 1e9;
- const int BUFF_SIZE = 1e5;
- int buffPos = BUFF_SIZE - 1;
- char buff[BUFF_SIZE];
- inline void readChar()
- {
- if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
- }
- inline void readString(char s[])
- {
- int pos = 0;
- for (; buff[buffPos] < '0' || buff[buffPos] > '1'; readChar());
- for (; buff[buffPos] >= '0' && buff[buffPos] <= '1'; readChar())
- s[pos++] = buff[buffPos];
- }
- inline void readInt(int &num)
- {
- num = 0;
- for (; buff[buffPos] < '0' || buff[buffPos] > '9'; readChar());
- for (; buff[buffPos] >= '0' && buff[buffPos] <= '9'; readChar())
- num = 10 * num + buff[buffPos] - '0';
- }
- int n, m;
- int g[MAXN];
- int perm[MAXN];
- int common[MAXN][MAXN];
- std::vector <int> v[MAXN];
- std::bitset <MAXN> bs[MAXN];
- std::bitset <MAXN> neighBS[MAXN];
- std::bitset <MAXN> neighNeighBS[MAXN];
- std::bitset <MAXN> pairs[MAXN];
- std::bitset <MAXN> neigh;
- std::bitset <MAXN> vis;
- void solve()
- {
- if (m > n * sqrt(n))
- {
- std::cout << 2 << '\n';
- return;
- }
- for (int i = 1 ; i <= n ; ++i)
- {
- vis.reset();
- for (const int &j : v[i])
- {
- for (const int &k : v[j])
- {
- if (i == k) continue;
- if (vis[k])
- {
- std::cout << 2 << '\n';
- return;
- }
- vis[k] = 1;
- common[i][k] = j;
- pairs[i][k] = 1;
- }
- }
- }
- for (int i = 1 ; i <= n ; ++i)
- {
- for (const int &j : v[i])
- {
- neighBS[i] |= bs[j];
- }
- }
- for (int i = 1 ; i <= n ; ++i)
- {
- for (const int &j : v[i])
- {
- neighNeighBS[i] |= neighBS[j];
- }
- neighNeighBS[i][i] = 0;
- }
- for (int i = 1 ; i <= n ; ++i)
- {
- for (int k = 1 ; k <= n ; ++k)
- {
- if (pairs[i][k] && bs[i][k] && g[common[i][k]] > 2)
- {
- std::cout << 3 << '\n';
- return;
- }
- }
- }
- for (int i = 1 ; i <= n ; ++i)
- {
- for (int k = i + 1 ; k <= n ; ++k)
- {
- if (!pairs[i][k] || bs[i][k]) continue;
- if (neighNeighBS[i][k])
- {
- std::cout << 3 << '\n';
- return;
- }
- }
- }
- for (int i = 1 ; i <= n ; ++i)
- {
- if (g[i] == 1) continue;
- for (const int &j : v[i])
- {
- if (g[i] >= 3 && g[j] >= 2)
- {
- std::cout << 4 << '\n';
- return;
- }
- if (g[i] == 2 && g[j] == 2)
- {
- int curr = v[i][0];
- if (curr == j) curr = v[i][1];
- int curr2 = v[j][0];
- if (curr2 == i) curr2 = v[j][1];
- if (curr != curr2)
- {
- std::cout << 4 << '\n';
- return;
- }
- }
- }
- }
- std::cout << -1 << '\n';
- }
- char s[MAXN];
- void input()
- {
- readInt(n);
- for (int i = 1 ; i < n ; ++i)
- {
- readString(s);
- for (int j = i + 1 ; j <= n ; ++j)
- {
- bs[i][j] = s[j - i - 1] - '0';
- bs[j][i] = s[j - i - 1] - '0';
- if (s[j - i - 1] == '1')
- {
- g[i]++; g[j]++;
- v[i].push_back(j);
- v[j].push_back(i);
- m++;
- }
- }
- }
- }
- void fastIO()
- {
- std::ios_base :: sync_with_stdio(0);
- std::cout.tie(nullptr);
- std::cin.tie(nullptr);
- }
- int main()
- {
- srand(229295);
- fastIO();
- input();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement