Much more efficiently, please! P21551


Statement
 

pdf   zip

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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;


const int INF = 1000000000;
typedef vector<int> VI;
typedef vector<VI> VVI;


int n, m;
VVI G;
int C[1000];


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<bool> 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
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Cinquè Concurs de Programació de la UPC - Final
    Date
    2007-10-03