結果

問題 No.1078 I love Matrix Construction
ユーザー micheeeeell1001micheeeeell1001
提出日時 2020-06-13 13:23:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 343 ms / 2,000 ms
コード長 4,682 bytes
コンパイル時間 2,732 ms
コンパイル使用メモリ 210,672 KB
実行使用メモリ 72,352 KB
最終ジャッジ日時 2023-09-07 07:35:33
合計ジャッジ時間 8,663 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 33 ms
13,700 KB
testcase_03 AC 112 ms
29,836 KB
testcase_04 AC 160 ms
39,936 KB
testcase_05 AC 132 ms
34,592 KB
testcase_06 AC 33 ms
13,116 KB
testcase_07 AC 12 ms
7,152 KB
testcase_08 AC 138 ms
33,760 KB
testcase_09 AC 6 ms
5,212 KB
testcase_10 AC 343 ms
72,352 KB
testcase_11 AC 171 ms
41,992 KB
testcase_12 AC 279 ms
60,660 KB
testcase_13 AC 308 ms
68,208 KB
testcase_14 AC 204 ms
48,184 KB
testcase_15 AC 291 ms
64,384 KB
testcase_16 AC 10 ms
6,684 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 25 ms
10,896 KB
testcase_19 AC 66 ms
20,528 KB
testcase_20 AC 63 ms
20,032 KB
testcase_21 AC 3 ms
4,420 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
ラムダ関数内,
    inlined from ‘int main()’ at main.cpp:166:17:
main.cpp:126:34: 警告: ‘t2’ may be used uninitialized [-Wmaybe-uninitialized]
  126 |         return 2 * (i * n + j) + k;
      |                                  ^
main.cpp: 関数 ‘int main()’ 内:
main.cpp:146:24: 備考: ‘t2’ はここで定義されています
  146 |         ll f1, f2, t1, t2;
      |                        ^~
ラムダ関数内,
    inlined from ‘int main()’ at main.cpp:165:17:
main.cpp:126:34: 警告: ‘f1’ may be used uninitialized [-Wmaybe-uninitialized]
  126 |         return 2 * (i * n + j) + k;
      |                                  ^
main.cpp: 関数 ‘int main()’ 内:
main.cpp:146:12: 備考: ‘f1’ はここで定義されています
  146 |         ll f1, f2, t1, t2;
      |            ^~
ラムダ関数内,
    inlined from ‘int main()’ at main.cpp:166:17:
main.cpp:126:34: 警告: ‘f2’ may be used uninitialized [-Wmaybe-uninitialized]
  126 |         return 2 * (i * n + j) + k;
      |                                  ^
main.cpp: 関数 ‘int main()’ 内:
main.cpp:146:16: 備考: ‘f2’ はここで定義されています
  146 |         ll f1, f2, t1, t2;
      |                ^~
ラムダ関数内,
    inlined from ‘int main()’ at main.cpp:165:17:
main.cpp:126:34: 警告: ‘t1’ may be used uninitialized [-Wmaybe-uninitialized]
  126 |         return 2 * (i * n + j) + k;
      |                                  ^
main.cpp: 関数 ‘int main()’ 内:
main.cpp:146:20: 備考: ‘t1’ はここで定義されています
  146 |         ll f1, f2, t1, t2;
      |                    ^~

ソースコード

diff # 

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 5e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char c) {return to_string((string) &c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template<class T>
bool chmax(T &a, T b){if(a < b){a = b; return true;} return false;}
template<class T>
bool chmin(T &a, T b){if(a > b){a = b; return true;} return false;}

int V;
vector<vector<ll>> g;
vector<vector<ll>> rg;
vector<ll> vs;
bool used[n_max];
vector<ll> cmp;
vector<vector<ll>> dag;
void add_edge(int f, int t){
    g[f].emplace_back(t);
    rg[t].emplace_back(f);
}

void dfs(ll v){
    used[v] = 1;
    for(auto &to : g[v]){
        if(!used[to]) dfs(to);
    }
    vs.emplace_back(v);
}

void rdfs(ll v, ll k){
    used[v] = 1;
    cmp[v] = k;
    for(auto &to : rg[v]){
        if(!used[to]) rdfs(to, k);
    }
}

int scc(){
    fill(used, used + n_max, 0);
    vs.clear();
    for(int v = 0; v < V; v++){
        if(!used[v])dfs(v);
    }
    fill(used, used + n_max, 0);
    ll k = 0;
    for(int i = vs.size()-1; i >= 0; i--){
        if(!used[vs[i]]) rdfs(vs[i], k++);
    }
    dag.resize(k);
    for(int i = 0; i < V; i++){
        for(auto &to : g[i]){
            int x = cmp[i], y = cmp[to];
            if(x == y)continue;
            dag[x].emplace_back(y);
        }
    }
    return k;
}
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    vector<ll> s(n);
    for(int i = 0; i < n; i++) cin >> s[i];
    vector<ll> t(n);
    for(int i = 0; i < n; i++) cin >> t[i];
    vector<ll> u(n);
    for(int i = 0; i < n; i++) cin >> u[i];
    rep(i,0,n){
        s[i]--;t[i]--;
    }
    auto node = [&](ll i, ll j, ll k){
        return 2 * (i * n + j) + k;
    };
    auto rev = [&](ll nd, ll* k) -> pair<ll, ll>{
        if(nd & 1){
            *k = 1;
            nd--;
        }
        else{
            *k = 0;
        }
        nd /= 2;
        return {nd / n, nd % n};
    };

    // ll k = 1;
    // debug(rev(10, &k));
    // debug(k);
    g.resize(n*n*2);rg.resize(n*n*2);cmp.resize(n*n*2);
    V = n * n * 2;
    rep(i,0,n)rep(j,0,n){
        ll f1, f2, t1, t2;

        if(u[i] == 0){
            f1 = f2 = 0;
            t1 = t2 = 1;
        }
        if(u[i] == 1){
            f1 = t1 = 1;
            f2 = t2 = 0;
        }
        if(u[i] == 2){
            f1 = t1 = 0;
            f2 = t2 = 1;
        }
        if(u[i] == 3){
            f1 = f2 = 1;
            t1 = t2 = 0;
        }
        // debug(s[i], j, t[i], node(s[i], j, f1), node(j, t[i], t1));
        add_edge(node(s[i], j, f1), node(j, t[i], t1));
        add_edge(node(j, t[i], f2), node(s[i], j, t2));
    }

    scc();
    debug(g);
    debug(cmp);

    rep(v,0,n*n){
        if(cmp[v*2] == cmp[v*2 + 1]){
            cout << -1 << endl;
            return 0;
        }
    }

    vector<vector<ll>> ans(n, vector<ll>(n));
    ll k = 0;
    rep(v, 0, n*n){
        if(cmp[v*2] > cmp[v*2 + 1]){
            auto p = rev(v*2, &k);
            ans[p.first][p.second] = k;
        }
        else{
            auto p = rev(v * 2 + 1, &k);
            ans[p.first][p.second] = k;
        }
    }

    for(auto &vec : ans){
        for(auto &t : vec){
            cout << t;
            if(&t != &vec.back()) cout << " ";
            else cout << "\n";
        }
    }
}
0