結果

問題 No.1078 I love Matrix Construction
ユーザー masutech16masutech16
提出日時 2020-06-22 22:27:46
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 254 ms / 2,000 ms
コード長 4,240 bytes
コンパイル時間 2,150 ms
コンパイル使用メモリ 180,588 KB
実行使用メモリ 48,016 KB
最終ジャッジ日時 2023-09-16 19:31:35
合計ジャッジ時間 6,779 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 24 ms
9,612 KB
testcase_03 AC 77 ms
20,020 KB
testcase_04 AC 109 ms
26,544 KB
testcase_05 AC 104 ms
22,464 KB
testcase_06 AC 20 ms
9,352 KB
testcase_07 AC 8 ms
5,432 KB
testcase_08 AC 93 ms
22,612 KB
testcase_09 AC 4 ms
4,376 KB
testcase_10 AC 254 ms
48,016 KB
testcase_11 AC 119 ms
27,852 KB
testcase_12 AC 190 ms
39,712 KB
testcase_13 AC 220 ms
44,396 KB
testcase_14 AC 130 ms
31,760 KB
testcase_15 AC 198 ms
42,328 KB
testcase_16 AC 7 ms
4,860 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 16 ms
7,808 KB
testcase_19 AC 34 ms
13,892 KB
testcase_20 AC 36 ms
13,528 KB
testcase_21 AC 3 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "/mnt/c/Users/leafc/dev/compro/lib/graph/SCC.hpp"

#include <cassert>
#include <iostream>
#include <vector>

#ifndef STRONGLY_CONNECTED_COMPONENTS
#define STRONGLY_CONNECTED_COMPONENTS

class StronglyConnectedComponents {
public:
  StronglyConnectedComponents(const std::vector<std::vector<int>> &g) {
    int n = g.size();
    std::vector<std::vector<int>> rg(n);
    for (int i = 0; i < n; i++) {
      for (const auto &v : g[i]) {
        rg[v].push_back(i);
      }
    }
    int now_id = 0;
    std::vector<int> id(n);
    std::vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
      now_id = dfs(i, now_id, id, visited, g);
    }

    int comp_id = 0;
    visited.assign(n, false);
    components_id.resize(n);
    for (int i = n - 1; i >= 0; i--) {
      rdfs(id[i], comp_id, visited, rg);
      comp_id++;
    }
  }

  int get(int i) const {
    assert(0 <= i && i < static_cast<int>(components_id.size()));
    return components_id[i];
  }

private:
  int dfs(int cur, int now_id, std::vector<int> &id, std::vector<bool> &visited,
          const std::vector<std::vector<int>> &g) {
    if (visited[cur])
      return now_id;
    visited[cur] = true;
    for (const auto &v : g[cur]) {
      now_id = dfs(v, now_id, id, visited, g);
    }
    id[now_id] = cur;
    now_id++;
    return now_id;
  }

  void rdfs(int cur, int comp_id, std::vector<bool> &visited, const std::vector<std::vector<int>> &g) {
    if (visited[cur])
      return;
    visited[cur] = true;
    components_id[cur] = comp_id;
    for (const auto v : g[cur]) {
      rdfs(v, comp_id, visited, g);
    }
  }

  std::vector<int> components_id;
};

using SCC = StronglyConnectedComponents;

#endif
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes, T no) { cout << (val ? yes : no) << "\n"; }

void say(bool val, string yes = "Yes", string no = "No") { say<string>(val, yes, no); }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}

// C++ 17に完全移行したら消す
// 最大公約数を求める
template <class T> T gcd(T n, T m) { return n ? gcd(m % n, n) : m; }

// 最小公倍数を求める
template <class T> T lcm(T n, T m) {
  int g = gcd(n, m);
  return n * m / g;
}

// 重複を消す。計算量はO(NlogN)
template <class T> void unique(std::vector<T> &v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
}


#line 3 "tmp.cpp"

int n;
int calc(int i, int j, bool b) { return i * n + j + (b ? 0 : n * n); }

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;

  vi s(n), t(n), u(n);
  REP(i, n) {
    cin >> s[i];
    s[i]--;
  }
  REP(i, n) {
    cin >> t[i];
    t[i]--;
  }
  REP(i, n) { cin >> u[i]; }

  vector<vector<int>> g(2 * n * n);

  REP(i, n) {
    REP(j, n) {
      if (u[i] == 0) {
        g[calc(s[i], j, false)].push_back(calc(j, t[i], true));
        g[calc(j, t[i], false)].push_back(calc(s[i], j, true));
      } else if (u[i] == 1) {
        g[calc(s[i], j, true)].push_back(calc(j, t[i], true));
        g[calc(j, t[i], false)].push_back(calc(s[i], j, false));
      } else if (u[i] == 2) {
        g[calc(s[i], j, false)].push_back(calc(j, t[i], false));
        g[calc(j, t[i], true)].push_back(calc(s[i], j, true));
      } else if (u[i] == 3) {
        g[calc(s[i], j, true)].push_back(calc(j, t[i], false));
        g[calc(j, t[i], true)].push_back(calc(s[i], j, false));
      }
    }
  }

  SCC scc(g);

  REP(i, n * n) {
    if (scc.get(i) == scc.get(n * n + i)) {
      cout << -1 << endl;
      return 0;
    }
  }

  vi ans(n * n, -1);
  REP(i, n * n) {
    if (scc.get(i) > scc.get(n * n + i)) {
      ans[i] = 1;
    } else {
      ans[i] = 0;
    }
  }

  REP(i, n) {
    REP(j, n) { cout << ans[i * n + j] << (j == n - 1 ? "\n" : " "); }
  }

  return 0;
}
0