結果
問題 | No.2277 Honest or Dishonest ? |
ユーザー |
![]() |
提出日時 | 2023-04-21 21:55:17 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 2,105 bytes |
コンパイル時間 | 1,026 ms |
コンパイル使用メモリ | 30,592 KB |
実行使用メモリ | 9,472 KB |
最終ジャッジ日時 | 2024-11-08 06:31:02 |
合計ジャッジ時間 | 4,603 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <stdio.h> typedef struct list { int v; struct list *n; } list; typedef struct tree { int v; struct tree *p; } tree; tree *get_root (tree *t) { if (t == NULL || t->p == NULL) { return t; } t->p = get_root(t->p); return t->p; } int func (int v, int b, list **e, int *flag, int *visited) { list *l = e[v]; if (visited[v] > 0 && flag[v] != b) { return -1; } else if (visited[v] > 0) { return 1; } visited[v] = 1; flag[v] = b; while (l != NULL) { if (func(l->v, 1-b, e, flag, visited) < 0) { return -1; } l = l->n; } return 1; } int main () { int n = 0; int q = 0; int a[100000] = {}; int b[100000] = {}; int c[100000] = {}; int res = 0; long long ans = 1LL; long long mod_num = 998244353LL; tree t[100000] = {}; list pool[200000] = {}; int used = 0; list *e[100000] = {}; int flag[100000] = {}; int visited[100000] = {}; res = scanf("%d", &n); res = scanf("%d", &q); for (int i = 0; i < q; i++) { res = scanf("%d", a+i); res = scanf("%d", b+i); res = scanf("%d", c+i); a[i]--; b[i]--; } for (int i = 0; i < n; i++) { t[i].v = i; t[i].p = NULL; } for (int i = 0; i < q; i++) { if (c[i] == 0) { tree *rt1 = get_root(t+a[i]); tree *rt2 = get_root(t+b[i]); if (rt1 != rt2) { rt2->p = rt1; } } } for (int i = 0; i < q; i++) { if (c[i] == 1) { tree *rt1 = get_root(t+a[i]); tree *rt2 = get_root(t+b[i]); if (rt1 == rt2) { ans = 0LL; } else { pool[used].v = rt2->v; pool[used].n = e[rt1->v]; e[rt1->v] = pool+used; used++; pool[used].v = rt1->v; pool[used].n = e[rt2->v]; e[rt2->v] = pool+used; used++; } } } for (int i = 0; i < n; i++) { if (t[i].p == NULL && visited[i] <= 0) { if (func(i, 0, e, flag, visited) < 0) { ans = 0LL; } else { ans *= 2LL; ans %= mod_num; } } } printf("%lld\n", ans); return 0; }