# Much more efficiently, please! P21551

Statement html

Write a program to computes the same as the program below, but much more efficiently, both in space and in time. The read variables n and m are such that 1 ≤ n ≤ 1000 and 0 ≤ m ≤ 10 n. Every given pair of x and y is such that xy.

||

 ``` #include #include #include using namespace std; const int INF = 1000000000; typedef vector VI; typedef vector VVI; int n, m; VVI G; int C; bool OK1(VVI A) { for (int x = 0; x < n; ++x) A[x][x] = 0; for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) A[i][j] = min(A[i][j], A[i][k] + A[k][j]); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (A[i][j] == INF) return false; return true; } ``` ``` bool OK2(int i) { if (i == n) return true; vector U(2, false); for (int j = 0; j < i; ++j) if (G[i][j] == 1) U[C[j]] = true; for (int k = 0; k < 2; ++k) if (not U[k]) { C[i] = k; if (OK2(i + 1)) return true; } return false; } int main() { while (cin >> n >> m) { G = VVI(n, VI(n, INF)); while (m--) { int x, y; cin >> x >> y; G[x][y] = G[y][x] = 1; } if (not OK1(G)) cout << "NC" << endl; else if (OK2(0)) cout << "yes" << endl; else cout << "no" << endl; } } ```

||

Public test cases
• Input

```5 4    0 1  1 3  2 4  3 0
6 7    0 1  1 2  2 3  3 4  4 5  5 0  0 3
5 5    2 1  0 1  3 4  4 0  2 3
```

Output

```NC
yes
no
```
• Information
Author