結果

問題 No.1078 I love Matrix Construction
ユーザー FF256grhyFF256grhy
提出日時 2023-08-23 18:19:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 407 ms / 2,000 ms
コード長 4,486 bytes
コンパイル時間 2,808 ms
コンパイル使用メモリ 218,636 KB
実行使用メモリ 93,504 KB
最終ジャッジ日時 2024-12-22 01:39:13
合計ジャッジ時間 9,040 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 50 ms
16,712 KB
testcase_03 AC 136 ms
37,752 KB
testcase_04 AC 188 ms
51,140 KB
testcase_05 AC 173 ms
43,252 KB
testcase_06 AC 41 ms
15,860 KB
testcase_07 AC 14 ms
8,124 KB
testcase_08 AC 167 ms
42,956 KB
testcase_09 AC 7 ms
5,248 KB
testcase_10 AC 407 ms
93,504 KB
testcase_11 AC 210 ms
53,936 KB
testcase_12 AC 330 ms
78,184 KB
testcase_13 AC 392 ms
87,212 KB
testcase_14 AC 254 ms
61,396 KB
testcase_15 AC 363 ms
83,352 KB
testcase_16 AC 12 ms
7,124 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 32 ms
12,968 KB
testcase_19 AC 88 ms
25,500 KB
testcase_20 AC 75 ms
25,104 KB
testcase_21 AC 4 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define dec(i, n)  decID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)

template<typename T> istream & operator>>(istream & s, vector<T> & v) { RF(e, v) { s >> e; } return s; }
template<typename T> ostream & operator<<(ostream & s, vector<T> const & v) {
	inc(i, SI(v)) { s << (i == 0 ? "" : " ") << v[i]; }
	return s;
}

#define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__);
void IN_() { };
template<typename T, typename ... U> void IN_(T &  a, U &  ... b) { cin >> a; IN_(b ...); };
template<typename T                > void OUT(T && a            ) { cout << a << endl; }
template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); }

// ---- ----

// https://beet-aizu.github.io/library/library/graph/stronglyconnectedcomponent.cpp.html
struct SCC{
  vector< vector<int> > G,R,T,C;
  vector<int> vs,used,blg;
  SCC(){}
  SCC(int n):G(n),R(n),used(n),blg(n){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    R[v].emplace_back(u);
  }

  void dfs(int v){
    used[v]=1;
    for(int u:G[v])
      if(!used[u]) dfs(u);
    vs.emplace_back(v);
  }

  void rdfs(int v,int k){
    used[v]=1;
    blg[v]=k;
    C[k].emplace_back(v);
    for(int u:R[v])
      if(!used[u]) rdfs(u,k);
  }

  int build(){
    int n=G.size();
    for(int v=0;v<n;v++)
      if(!used[v]) dfs(v);

    fill(used.begin(),used.end(),0);
    int k=0;
    for(int i=n-1;i>=0;i--){
      if(!used[vs[i]]){
        T.emplace_back();
        C.emplace_back();
        rdfs(vs[i],k++);
      }
    }

    for(int v=0;v<n;v++)
      for(int u:G[v])
        if(blg[v]!=blg[u])
          T[blg[v]].push_back(blg[u]);

    for(int i=0;i<k;i++){
      sort(T[i].begin(),T[i].end());
      T[i].erase(unique(T[i].begin(),T[i].end()),T[i].end());
    }
    return k;
  }

  int operator[](int k) const{return blg[k];}
};

// https://beet-aizu.github.io/library/library/graph/twosatisfiability.cpp.html
struct TwoSat{
  int n;
  SCC scc;
  TwoSat(int n):n(n),scc(n*2){}
  int negate(int v){return (n+v)%(n*2);}
  void add_if(int u,int v){
    // u -> v <=> !v -> !u
    scc.add_edge(u,v);
    scc.add_edge(negate(v),negate(u));
  }
  void add_or(int u,int v){
    // u or v <=> !u -> v
    add_if(negate(u),v);
  }
  void add_nand(int u,int v){
    // u nand v <=> u -> !v
    add_if(u,negate(v));
  }
  void set_true(int v){
    //  v <=> !v ->  v
    scc.add_edge(negate(v),v);
  }
  void set_false(int v){
    // !v <=>  v -> !v
    scc.add_edge(v,negate(v));
  }
  vector<int> build(){
    scc.build();
    vector<int> res(n);
    for(int i=0;i<n;i++){
      if(scc[i]==scc[n+i]) return {};
      res[i]=scc[i]>scc[n+i];
    }
    return res;
  }
};

int main() {
	IN(int, n);
	vector<int> s(n), t(n), u(n);
	cin >> s >> t >> u;
	inc(i, n) {
		s[i]--;
		t[i]--;
	}
	
	auto id = [&](int i, int j) { return n * i + j; };
	
	TwoSat ts(n * n);
	inc(i, n) {
	inc(j, n) {
		int a = id(s[i], j);
		int b = id(j, t[i]);
		int A = ts.negate(a);
		int B = ts.negate(b);
		if(u[i] == 0) { ts.add_or(a, b); }
		if(u[i] == 1) { ts.add_or(A, b); }
		if(u[i] == 2) { ts.add_or(a, B); }
		if(u[i] == 3) { ts.add_or(A, B); }
	}
	}
	auto res = ts.build();
	if(res.empty()) { OUT(-1); } else {
		inc(i, n) {
			vector<int> v;
			inc(j, n) { v.PB(res[id(i, j)] ? 1 : 0); }
			OUT(v);
		}
	}
}
0