結果

問題 No.1078 I love Matrix Construction
ユーザー miyo2580miyo2580
提出日時 2022-08-09 01:03:16
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 5,033 bytes
コンパイル時間 2,662 ms
コンパイル使用メモリ 222,008 KB
実行使用メモリ 19,060 KB
最終ジャッジ日時 2024-09-19 08:47:44
合計ジャッジ時間 5,700 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 7 ms
5,484 KB
testcase_03 AC 19 ms
9,072 KB
testcase_04 AC 21 ms
11,248 KB
testcase_05 AC 23 ms
9,708 KB
testcase_06 AC 7 ms
5,488 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 18 ms
10,228 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 45 ms
19,060 KB
testcase_11 AC 22 ms
11,760 KB
testcase_12 AC 34 ms
15,860 KB
testcase_13 AC 40 ms
17,904 KB
testcase_14 AC 28 ms
13,292 KB
testcase_15 AC 39 ms
16,752 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 6 ms
5,376 KB
testcase_19 AC 11 ms
7,020 KB
testcase_20 AC 10 ms
6,888 KB
testcase_21 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
using Graph = vector<vector<ll>>;
const long long INF = 1LL<<60;
const long long MOD = 1000000007; 

//https://nyaannyaan.github.io/library/math/two-sat.hpp.html

namespace TwoSatImpl {
namespace internal {

template <class E>
struct csr {
  vector<int> start;
  vector<E> elist;
  csr(int n, const vector<pair<int, E>>& edges)
      : start(n + 1), elist(edges.size()) {
    for (auto e : edges) {
      start[e.first + 1]++;
    }
    for (int i = 1; i <= n; i++) {
      start[i] += start[i - 1];
    }
    auto counter = start;
    for (auto e : edges) {
      elist[counter[e.first]++] = e.second;
    }
  }
};

struct scc_graph {
 public:
  scc_graph(int n) : _n(n) {}

  int num_vertices() { return _n; }

  void add_edge(int from, int to) { edges.push_back({from, {to}}); }

  pair<int, vector<int>> scc_ids() {
    auto g = csr<edge>(_n, edges);
    int now_ord = 0, group_num = 0;
    vector<int> visited, low(_n), ord(_n, -1), ids(_n);
    visited.reserve(_n);
    auto dfs = [&](auto self, int v) -> void {
      low[v] = ord[v] = now_ord++;
      visited.push_back(v);
      for (int i = g.start[v]; i < g.start[v + 1]; i++) {
        auto to = g.elist[i].to;
        if (ord[to] == -1) {
          self(self, to);
          low[v] = min(low[v], low[to]);
        } else {
          low[v] = min(low[v], ord[to]);
        }
      }
      if (low[v] == ord[v]) {
        while (true) {
          int u = visited.back();
          visited.pop_back();
          ord[u] = _n;
          ids[u] = group_num;
          if (u == v) break;
        }
        group_num++;
      }
    };
    for (int i = 0; i < _n; i++) {
      if (ord[i] == -1) dfs(dfs, i);
    }
    for (auto& x : ids) {
      x = group_num - 1 - x;
    }
    return {group_num, ids};
  }

  vector<vector<int>> scc() {
    auto ids = scc_ids();
    int group_num = ids.first;
    vector<int> counts(group_num);
    for (auto x : ids.second) counts[x]++;
    vector<vector<int>> groups(ids.first);
    for (int i = 0; i < group_num; i++) {
      groups[i].reserve(counts[i]);
    }
    for (int i = 0; i < _n; i++) {
      groups[ids.second[i]].push_back(i);
    }
    return groups;
  }

  void add_node_size(int m) { _n += m; }
  int size() { return _n; }

 private:
  int _n;
  struct edge {
    int to;
  };
  vector<pair<int, edge>> edges;
};

}  // namespace internal

struct two_sat {
 public:
  two_sat() : _n(0), built(false), scc(0) {}
  two_sat(int n) : _n(n), built(false), scc(2 * n) {}

  int add_var() {
    scc.add_node_size(2);
    return _n++;
  }

  // (not i) は ~i で渡す
  void add_clause(int i, int j) {
    i = max(2 * i, -1 - 2 * i);
    j = max(2 * j, -1 - 2 * j);
    assert(0 <= i && i < 2 * _n);
    assert(0 <= j && j < 2 * _n);
    scc.add_edge(i, j ^ 1);
    scc.add_edge(j, i ^ 1);
  }
  void if_then(int i, int j) { add_clause(~i, j); }
  void set_val(int i) { add_clause(i, i); }

  // (not i) は ~i で渡す
  void at_most_one(const vector<int>& nodes) {
    if ((int)nodes.size() <= 1) return;
    int cur = ~nodes[0];
    for (int i = 2; i < (int)nodes.size(); i++) {
      int nxt = add_var(), n_i = ~nodes[i];
      add_clause(cur, n_i);
      add_clause(cur, nxt);
      add_clause(n_i, nxt);
      cur = ~nxt;
    }
    add_clause(cur, ~nodes[1]);
  }

  bool satisfiable() {
    _answer.resize(_n);
    built = true;
    auto id = scc.scc_ids().second;
    for (int i = 0; i < _n; i++) {
      if (id[2 * i] == id[2 * i + 1]) {
        _answer.clear();
        return false;
      }
      _answer[i] = id[2 * i] < id[2 * i + 1];
    }
    return true;
  }
  vector<bool> answer() {
    if (!built) satisfiable();
    return _answer;
  }

 private:
  int _n;
  vector<bool> _answer;
  bool built;
  internal::scc_graph scc;
};

}  // namespace TwoSatImpl

using TwoSatImpl::two_sat;


int main()
{  
    ios::sync_with_stdio(false);
    cin.tie(0);  
    ll n;cin>>n;
    vec s(n),t(n),u(n);
    rep(i,n)cin>>s[i];
    rep(i,n)cin>>t[i];
    rep(i,n)cin>>u[i];
    rep(i,n){s[i]--;t[i]--;}
    two_sat ts(n*n);
    rep(i,n)rep(j,n){
       ll x=s[i]*n+j;
       ll y=j*n+t[i];
       if(u[i]==0){
          ts.add_clause(x,y);
       }
       if(u[i]==1){
          ts.add_clause(~x,y);
       }
       if(u[i]==2){
          ts.add_clause(x,~y);
       }
       if(u[i]==3){
         ts.add_clause(~x,~y);
       }
    }
    if(ts.satisfiable()){
       auto v=ts.answer();
       rep(i,n)rep(j,n){
          ll x=i*n+j;
          if(v[x])cout<<1;
          else cout<<0;
          if(j==n-1)cout<<endl;
          else cout<<' ';
       }
    }
    else cout<<-1<<endl;
    return 0;
}
0