Submission #1403763

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;

/**
 * Strong connected components.
 * Header requirement: algorithm, cassert, set, vector
 * Verified by: AtCoder ARC010 (http://arc010.contest.atcoder.jp/submissions/1015294)
 *              yukicoder No. 19 (http://yukicoder.me/submissions/141513)
 */
class SCC {
private:
  int n;
  int ncc;
  typedef std::vector<int> vi;
  std::vector<vi> g; // graph in adjacent list
  std::vector<vi> rg; // reverse graph
  vi vs;
  std::vector<bool> used;
  vi cmp;
public:
  SCC(int n): n(n), ncc(-1), g(n), rg(n), vs(n), used(n), cmp(n) {}
  void add_edge(int from, int to) {
    g[from].push_back(to);
    rg[to].push_back(from);
  }
private:
  void dfs(int v) {
    used[v] = true;
    for (int i = 0; i < g[v].size(); ++i) {
      if (!used[g[v][i]]) { dfs(g[v][i]); }
    }
    vs.push_back(v);
  }
  void rdfs(int v, int k) {
    used[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rg[v].size(); ++i) {
      if (!used[rg[v][i]]) { rdfs(rg[v][i], k); }
    }
  }
public:
  int scc() {
    std::fill(used.begin(), used.end(), 0);
    vs.clear();
    for (int v = 0; v < n; ++v) {
      if (!used[v]) { dfs(v); }
    }
    std::fill(used.begin(), used.end(), 0);
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; --i) {
      if (!used[vs[i]]) { rdfs(vs[i], k++); }
    }
    return ncc = k;
  }
  std::vector<int> top_order() const {
    if (ncc == -1) assert(0);
    return cmp;
  }
  std::vector<std::vector<int> > scc_components(void) const {
    if (ncc == -1) assert(0);
    std::vector<std::vector<int> > ret(ncc);
    for (int i = 0; i < n; ++i) {
      ret[cmp[i]].push_back(i);
    }
    return ret;
  }
  /*
   * Returns a dag whose vertices are scc's, and whose edges are those of the original graph, in the adjacent-list format.
   */
  std::vector<std::vector<int> > dag() const {
    if (ncc == -1) {
      assert(0);
    }
    typedef std::set<int> si;
    std::vector<si> ret(ncc);
    for (int i = 0; i < g.size(); ++i) {
      for (int j = 0; j < g[i].size(); ++j) {
	int to = g[i][j];
	if (cmp[i] != cmp[to]) {
	  assert (cmp[i] < cmp[to]);
	  ret[cmp[i]].insert(cmp[to]);
	}
      }
    }
    std::vector<std::vector<int> > vret(ncc);
    for (int i = 0; i < ncc; ++i) {
      vret[i] = std::vector<int>(ret[i].begin(), ret[i].end());
    }
    return vret;
  }
  std::vector<std::vector<int> > rdag() const {
    if (ncc == -1) {
      assert(0);
    }
    typedef std::set<int> si;
    std::vector<si> ret(ncc);
    for (int i = 0; i < (int) g.size(); ++i) {
      for (int j = 0; j < (int) g[i].size(); ++j) {
	int to = g[i][j];
	if (cmp[i] != cmp[to]) {
	  assert (cmp[i] < cmp[to]);
	  ret[cmp[to]].insert(cmp[i]);
	}
      }
    }
    std::vector<std::vector<int> > vret(ncc);
    for (int i = 0; i < ncc; ++i) {
      vret[i] = std::vector<int>(ret[i].begin(), ret[i].end());
    }
    return vret;
  }
};



const int inf = 1000;

int main(void){
  int n;
  cin >> n;
  VI a(n);
  vector<PI> pool;
  REP(i, 0, n) {
    cin >> a[i];
    pool.push_back(PI(a[i], i));
  }
  sort(pool.begin(), pool.end());
  int h, w;
  cin >> h >> w;
  vector<VI> b(h, VI(w));
  vector<PI> mi(n, PI(inf, inf)), ma(n, PI(-inf, -inf));
  REP(i, 0, h) {
    REP(j, 0, w) {
      cin >> b[i][j];
      int c = b[i][j];
      mi[c].first = min(mi[c].first, i);
      mi[c].second = min(mi[c].second, j);
      ma[c].first = max(ma[c].first, i);
      ma[c].second = max(ma[c].second, j);
    }
  }
  // Collect constraints, O(nhw)
  vector<VI> cons(n, VI(n, 0));
  REP(i, 0, h) {
    REP(j, 0, w) {
      int c = b[i][j];
      REP(k, 0, n) {
	if (k == c) { continue; }
	if (mi[k].first <= i && i <= ma[k].first &&
	    mi[k].second <= j && j <= ma[k].second) {
	  cons[k][c] = 1; // k -> c
	}
      }
    }
  }
  SCC scc(n);
  REP(i, 0, n) {
    REP(j, 0, n) {
      if (cons[i][j]) {
	scc.add_edge(i, j);
      }
    }
  }
  int ncc = scc.scc();
  if (ncc < n) {
    cout << 0 << endl;
    return 0;
  }
  vector<VI> dist(n, VI(n, inf));
  REP(i, 0, n) {
    REP(j, 0, n) {
      dist[i][j] = cons[i][j] ? 0 : inf;
    }
  }
  REP(k, 0, n) {
    REP(i, 0, n) {
      REP(j, 0, n) {
	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  assert (n <= 10);
  // Try all possibilities, O(n!n^2)
  VI perm(n);
  REP(i, 0, n) {
    perm[i] = i;
  }
  bool ok = false;
  do {
    bool valid = true;
    REP(i, 0, n) {
      REP(j, 0, n) {
	// i -> j implies a[perm[i]] < a[perm[j]]
	if (cons[i][j] && a[perm[i]] >= a[perm[j]]) {
	  valid = false;
	}
      }
    }
    if (not valid) {
      continue;
    }
    ok = true;
  } while (next_permutation(perm.begin(), perm.end()) && not ok);
  cout << (ok ? 1 : 0) << endl;
}

Submission Info

Judge Result