結果

問題 No.2277 Honest or Dishonest ?
ユーザー magsta
提出日時 2023-04-19 15:23:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 5,235 bytes
コンパイル時間 976 ms
コンパイル使用メモリ 73,856 KB
実行使用メモリ 20,864 KB
最終ジャッジ日時 2024-11-08 06:20:03
合計ジャッジ時間 8,176 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 19 WA * 31
権限があれば一括ダウンロードができます

ソースコード

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

#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 (a == b) cout << -1 << endl;
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) % 1000000007;
}
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0