#860859 (C++14) No.2277 Honest or Dishonest ?

提出ソース

結果

問題	No.2277 Honest or Dishonest ?
ユーザー	magsta
提出日時	2023-04-20 09:31:48
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	231 ms / 2,000 ms
コード長	5,194 bytes
コンパイル時間	1,070 ms
コンパイル使用メモリ	73,460 KB
実行使用メモリ	20,736 KB
最終ジャッジ日時	2024-11-08 06:20:13
合計ジャッジ時間	9,380 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	168 ms 15,360 KB
testcase_04	AC	182 ms 18,048 KB
testcase_05	AC	51 ms 12,672 KB
testcase_06	AC	129 ms 11,520 KB
testcase_07	AC	112 ms 11,904 KB
testcase_08	AC	42 ms 13,440 KB
testcase_09	AC	110 ms 13,696 KB
testcase_10	AC	68 ms 8,576 KB
testcase_11	AC	33 ms 6,272 KB
testcase_12	AC	44 ms 5,248 KB
testcase_13	AC	147 ms 13,312 KB
testcase_14	AC	50 ms 5,248 KB
testcase_15	AC	42 ms 11,008 KB
testcase_16	AC	103 ms 11,520 KB
testcase_17	AC	43 ms 7,168 KB
testcase_18	AC	152 ms 17,408 KB
testcase_19	AC	168 ms 17,536 KB
testcase_20	AC	138 ms 14,336 KB
testcase_21	AC	94 ms 8,320 KB
testcase_22	AC	101 ms 12,672 KB
testcase_23	AC	115 ms 8,832 KB
testcase_24	AC	89 ms 12,160 KB
testcase_25	AC	118 ms 15,488 KB
testcase_26	AC	25 ms 12,288 KB
testcase_27	AC	57 ms 7,040 KB
testcase_28	AC	44 ms 10,624 KB
testcase_29	AC	77 ms 13,056 KB
testcase_30	AC	61 ms 8,448 KB
testcase_31	AC	123 ms 12,800 KB
testcase_32	AC	66 ms 12,416 KB
testcase_33	AC	153 ms 17,152 KB
testcase_34	AC	172 ms 16,256 KB
testcase_35	AC	14 ms 8,704 KB
testcase_36	AC	99 ms 11,520 KB
testcase_37	AC	134 ms 11,520 KB
testcase_38	AC	23 ms 5,248 KB
testcase_39	AC	38 ms 5,888 KB
testcase_40	AC	15 ms 7,424 KB
testcase_41	AC	176 ms 17,024 KB
testcase_42	AC	145 ms 13,440 KB
testcase_43	AC	227 ms 20,736 KB
testcase_44	AC	203 ms 20,736 KB
testcase_45	AC	196 ms 20,736 KB
testcase_46	AC	229 ms 20,736 KB
testcase_47	AC	222 ms 20,736 KB
testcase_48	AC	212 ms 20,736 KB
testcase_49	AC	207 ms 20,736 KB
testcase_50	AC	198 ms 20,736 KB
testcase_51	AC	216 ms 20,736 KB
testcase_52	AC	231 ms 20,736 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

// 深さ優先探索
int seen[100010], seen2[100010];
bool dfs(const Graph &G, const Graph &G_, const Graph &G2, const Graph &G2_, int v, bool HonLia) {
    bool flag = false; //矛盾が生じたか
    if (HonLia == true) seen[v] = 2;
    else seen[v] = 1;
    for (auto next_v : G[v]) { 
        if (seen[next_v] >= 1){
            if (HonLia == true && seen[next_v] == 1) flag = true;
            if (HonLia == false && seen[next_v] == 2) flag = true;
            continue;
        }
        if (HonLia == true) {if (dfs(G, G_, G2, G2_, next_v, true) == true) flag = true;} // 再帰的に探索
        else {if (dfs(G, G_, G2, G2_, next_v, false) == true) flag = true;} // 再帰的に探索
    }
    for (auto next_v : G_[v]) { 
        if (seen[next_v] >= 1){
            if (HonLia == true && seen[next_v] == 2) flag = true;
            if (HonLia == false && seen[next_v] == 1) flag = true;
            continue;
        }
        if (HonLia == true) {if (dfs(G, G_, G2, G2_, next_v, false) == true) flag = true;} // 再帰的に探索
        else {if (dfs(G, G_, G2, G2_, next_v, true) == true) flag = true;} // 再帰的に探索
    }
    for (auto next_v : G2[v]) { 
        if (seen[next_v] >= 1){
            if (HonLia == true && seen[next_v] == 1) flag = true;
            if (HonLia == false && seen[next_v] == 2) flag = true;
            continue;
        }
        if (HonLia == true) {if (dfs(G, G_, G2, G2_, next_v, true) == true) flag = true;} // 再帰的に探索
        else {if (dfs(G, G_, G2, G2_, next_v, false) == true) flag = true;} // 再帰的に探索
    }
    for (auto next_v : G2_[v]) { 
        if (seen[next_v] >= 1){
            if (HonLia == true && seen[next_v] == 2) flag = true;
            if (HonLia == false && seen[next_v] == 1) flag = true;
            continue;
        }
        if (HonLia == true) {if (dfs(G, G_, G2, G2_, next_v, false) == true) flag = true;} // 再帰的に探索
        else {if (dfs(G, G_, G2, G2_, next_v, true) == true) flag = true;} // 再帰的に探索
    }
    return flag;
}
bool dfs2(const Graph &G, const Graph &G_, const Graph &G2, const Graph &G2_, int v, bool HonLia) {
    bool flag = false; //矛盾が生じたか
    if (HonLia == true) seen2[v] = 2;
    else seen2[v] = 1;
    for (auto next_v : G[v]) { 
        if (seen2[next_v] >= 1){
            if (HonLia == true && seen2[next_v] == 1) flag = true;
            if (HonLia == false && seen2[next_v] == 2) flag = true;
            continue;
        }
        if (HonLia == true) {if (dfs2(G, G_, G2, G2_, next_v, true) == true) flag = true;} // 再帰的に探索
        else {if (dfs2(G, G_, G2, G2_, next_v, false) == true) flag = true;} // 再帰的に探索
    }
    for (auto next_v : G_[v]) { 
        if (seen2[next_v] >= 1){
            if (HonLia == true && seen2[next_v] == 2) flag = true;
            if (HonLia == false && seen2[next_v] == 1) flag = true;
            continue;
        }
        if (HonLia == true) {if (dfs2(G, G_, G2, G2_, next_v, false) == true) flag = true;} // 再帰的に探索
        else {if (dfs2(G, G_, G2, G2_, next_v, true) == true) flag = true;} // 再帰的に探索
    }
    for (auto next_v : G2[v]) { 
        if (seen2[next_v] >= 1){
            if (HonLia == true && seen2[next_v] == 1) flag = true;
            if (HonLia == false && seen2[next_v] == 2) flag = true;
            continue;
        }
        if (HonLia == true) {if (dfs2(G, G_, G2, G2_, next_v, true) == true) flag = true;} // 再帰的に探索
        else {if (dfs2(G, G_, G2, G2_, next_v, false) == true) flag = true;} // 再帰的に探索
    }
    for (auto next_v : G2_[v]) { 
        if (seen2[next_v] >= 1){
            if (HonLia == true && seen2[next_v] == 2) flag = true;
            if (HonLia == false && seen2[next_v] == 1) flag = true;
            continue;
        }
        if (HonLia == true) {if (dfs2(G, G_, G2, G2_, next_v, false) == true) flag = true;} // 再帰的に探索
        else {if (dfs2(G, G_, G2, G2_, next_v, true) == true) flag = true;} // 再帰的に探索
    }
    return flag;
}

int main() {
    // 頂点数と辺数
    int N, Q; cin >> N >> Q;

    // グラフ入力受取
    Graph G(N), G_(N), G2(N), G2_(N);
    for (int i = 0; i < Q; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        if (c == 0) G[a - 1].push_back(b - 1);
        if (c == 1) G_[a - 1].push_back(b - 1);
        if (c == 0) G2[b - 1].push_back(a - 1);
        if (c == 1) G2_[b - 1].push_back(a - 1);
    }

    // 全頂点が訪問済みになるまで探索
    long long ans = 1;
    for (int i = 0; i < N; i++) seen[i] = seen2[i] = 0;
    for (int v = 0; v < N; ++v) {
        if (seen[v] >= 1) continue; // v が探索済みだったらスルー
        long long count = 0;
        if (dfs(G, G_, G2, G2_, v, true) == false) count++; // v が未探索なら v を始点とした DFS を行う
        if (dfs2(G, G_, G2, G2_, v, false) == false) count++; // v が未探索なら v を始点とした DFS を行う
        ans = (ans * count) % 998244353;
    }
    cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード