結果

問題 No.1078 I love Matrix Construction
ユーザー ok
提出日時 2020-06-13 01:34:33
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 329 ms / 2,000 ms
コード長 3,661 bytes
コンパイル時間 1,257 ms
コンパイル使用メモリ 99,728 KB
実行使用メモリ 69,176 KB
最終ジャッジ日時 2024-06-24 06:15:21
合計ジャッジ時間 6,359 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
#define int long long
#define endl "\n"
constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 
struct fast_io {
    fast_io(){
        std::cin.tie(nullptr);
        std::ios::sync_with_stdio(false);
    };
} fio;
void dfs1(vector<vector<pair<int,int>>> &graph, vector<int> &num, vector<int> &used, int node, int &con){
        
        if(used[node]) return ;
        
        used[node] = true;
        
        for(pair<int,int> next : graph[node]){
                dfs1(graph, num, used, next.first, con);
        }
        
        num[con++] = node;
}
void dfs2(vector<vector<pair<int,int>>> &graph, vector<int> &scc, vector<int> &used, int node, int same){
        
        if(used[node]) return ;
        
        used[node] = true;
        
        for(pair<int,int> next : graph[node]){
                dfs2(graph, scc, used, next.first, same);
        }
        
        scc[node] = same;
}
void Strongly_Connected_Components(vector<vector<pair<int,int>>> &graph, vector<int> &scc){
        vector<int>  used(graph.size()), num(graph.size());
        vector<vector<pair<int,int>>> graph2(graph.size());
        int con = 0;
        
        scc.resize(graph.size());
        
        for(int i = 0; i < graph.size(); i++){
                dfs1(graph, num, used, i, con);
        }
        
        for(int i = 0; i < graph.size(); i++){
                for(int j = 0; j < graph[i].size(); j++){
                        graph2[graph[i][j].first].push_back(make_pair(i, graph[i][j].second));
                }
        }
        
        used.clear();
        used.resize(graph.size());
        
        for(int i = (int)graph.size()-1, same = 0; i >= 0; i--){
                if(!used[num[i]]){
                        dfs2(graph2, scc, used, num[i], same);
                        same++;
                }
        }
        
}
bool two_satisfiability(int num, vector<pair<pair<bool,int>,pair<bool,int>>>& closure, vector<bool>& val){
    vector<vector<pair<int,int>>> graph(num*2);
    vector<int> scc;
    
    val.resize(num);
    
    for(int i = 0; i < closure.size(); i++){
        graph[!closure[i].first.first + closure[i].first.second*2].push_back({closure[i].second.first  + closure[i].second.second*2 ,0});
        graph[!closure[i].second.first + closure[i].second.second*2].push_back({closure[i].first.first  + closure[i].first.second*2 ,0});
    }
    
    Strongly_Connected_Components(graph, scc);
    
    for(int i = 0; i < num*2; i += 2){
        if(scc[i] == scc[i+1]){
            return false;
        } else if(scc[i] > scc[i+1]){
            val[i/2] = true;
        } else {
            val[i/2] = false;
        }
    }
    return true;
}
bool check(pair<int,int> a, pair<int,int> b){
    bool res;
    
    res = (a.second - a.first + 1 + b.second - b.first + 1 > max(a.second, b.second) - min(a.first, b.first) + 1);
    
    return res;
}
signed main(){
    cout<<fixed<<setprecision(10);
    
    int N;
    vector<int> S, T, U;
    vector<pair<pair<bool,int>,pair<bool,int>>> closure;
    vector<bool> val;
    cin>>N;
    
    S.resize(N);
    T.resize(N);
    U.resize(N);
    
    for(int i = 0; i < N; i++){
        cin>>S[i];
        S[i]--;
    }
    
    for(int i = 0; i < N; i++){
        cin>>T[i];
        T[i]--;
    }
    
    for(int i = 0; i < N; i++){
        cin>>U[i];
    }
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            closure.push_back({{U[i]%2, S[i] * N + j},{U[i]/2, j * N + T[i]}});
        }
    }
    
    if(two_satisfiability(N * N, closure, val)) {
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(j) cout<<" "; 
                cout<<val[i * N + j];
            }
            cout<<endl;
        }
    } else {
        cout<<-1<<endl;
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0