結果

問題 No.1078 I love Matrix Construction
ユーザー micheeeeell1001micheeeeell1001
提出日時 2020-06-13 13:23:01
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 319 ms / 2,000 ms
コード長 4,682 bytes
コンパイル時間 2,660 ms
コンパイル使用メモリ 212,876 KB
実行使用メモリ 72,580 KB
最終ジャッジ日時 2024-06-25 01:55:53
合計ジャッジ時間 7,237 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 28 ms
13,924 KB
testcase_03 AC 94 ms
29,960 KB
testcase_04 AC 133 ms
40,204 KB
testcase_05 AC 123 ms
34,752 KB
testcase_06 AC 26 ms
13,388 KB
testcase_07 AC 11 ms
7,296 KB
testcase_08 AC 104 ms
34,028 KB
testcase_09 AC 6 ms
5,376 KB
testcase_10 AC 319 ms
72,580 KB
testcase_11 AC 144 ms
42,184 KB
testcase_12 AC 246 ms
60,780 KB
testcase_13 AC 276 ms
67,864 KB
testcase_14 AC 193 ms
48,072 KB
testcase_15 AC 283 ms
64,632 KB
testcase_16 AC 10 ms
6,656 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 22 ms
11,112 KB
testcase_19 AC 54 ms
20,504 KB
testcase_20 AC 56 ms
20,144 KB
testcase_21 AC 3 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
In lambda function,
    inlined from 'int main()' at main.cpp:166:17:
main.cpp:126:34: warning: 't2' may be used uninitialized [-Wmaybe-uninitialized]
  126 |         return 2 * (i * n + j) + k;
      |                                  ^
main.cpp: In function 'int main()':
main.cpp:146:24: note: 't2' was declared here
  146 |         ll f1, f2, t1, t2;
      |                        ^~
In lambda function,
    inlined from 'int main()' at main.cpp:165:17:
main.cpp:126:34: warning: 'f1' may be used uninitialized [-Wmaybe-uninitialized]
  126 |         return 2 * (i * n + j) + k;
      |                                  ^
main.cpp: In function 'int main()':
main.cpp:146:12: note: 'f1' was declared here
  146 |         ll f1, f2, t1, t2;
      |            ^~
In lambda function,
    inlined from 'int main()' at main.cpp:166:17:
main.cpp:126:34: warning: 'f2' may be used uninitialized [-Wmaybe-uninitialized]
  126 |         return 2 * (i * n + j) + k;
      |                                  ^
main.cpp: In function 'int main()':
main.cpp:146:16: note: 'f2' was declared here
  146 |         ll f1, f2, t1, t2;
      |                ^~
In lambda function,
    inlined from 'int main()' at main.cpp:165:17:
main.cpp:126:34: warning: 't1' may be used uninitialized [-Wmaybe-uninitialized]
  126 |         return 2 * (i * n + j) + k;
      |                                  ^
main.cpp: In function 'int main()':
main.cpp:146:20: note: 't1' was declared here
  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