結果
問題 | No.1612 I hate Construct a Palindrome |
ユーザー | 👑 ygussany |
提出日時 | 2021-05-22 23:59:18 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 2,694 bytes |
コンパイル時間 | 349 ms |
コンパイル使用メモリ | 31,524 KB |
実行使用メモリ | 10,572 KB |
最終ジャッジ日時 | 2023-09-24 14:27:14 |
合計ジャッジ時間 | 6,174 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,684 KB |
testcase_01 | AC | 2 ms
4,792 KB |
testcase_02 | AC | 60 ms
9,988 KB |
testcase_03 | AC | 2 ms
4,940 KB |
testcase_04 | AC | 2 ms
4,680 KB |
testcase_05 | AC | 61 ms
8,692 KB |
testcase_06 | AC | 41 ms
7,444 KB |
testcase_07 | AC | 42 ms
7,472 KB |
testcase_08 | AC | 39 ms
9,352 KB |
testcase_09 | AC | 35 ms
7,296 KB |
testcase_10 | AC | 37 ms
7,456 KB |
testcase_11 | AC | 37 ms
7,264 KB |
testcase_12 | AC | 40 ms
7,664 KB |
testcase_13 | AC | 41 ms
7,564 KB |
testcase_14 | AC | 41 ms
7,652 KB |
testcase_15 | AC | 75 ms
10,244 KB |
testcase_16 | AC | 74 ms
10,208 KB |
testcase_17 | AC | 74 ms
10,572 KB |
testcase_18 | AC | 2 ms
4,644 KB |
testcase_19 | AC | 2 ms
4,636 KB |
testcase_20 | AC | 2 ms
4,668 KB |
testcase_21 | AC | 2 ms
4,736 KB |
testcase_22 | AC | 2 ms
4,664 KB |
testcase_23 | AC | 2 ms
4,728 KB |
testcase_24 | AC | 2 ms
4,548 KB |
testcase_25 | AC | 2 ms
4,896 KB |
testcase_26 | AC | 2 ms
4,768 KB |
testcase_27 | AC | 2 ms
4,692 KB |
testcase_28 | AC | 2 ms
4,752 KB |
testcase_29 | AC | 2 ms
5,172 KB |
testcase_30 | AC | 2 ms
4,756 KB |
testcase_31 | AC | 2 ms
4,592 KB |
testcase_32 | AC | 2 ms
5,092 KB |
testcase_33 | AC | 2 ms
5,032 KB |
testcase_34 | AC | 2 ms
4,676 KB |
testcase_35 | AC | 2 ms
4,608 KB |
testcase_36 | AC | 2 ms
4,676 KB |
testcase_37 | AC | 2 ms
4,672 KB |
testcase_38 | AC | 2 ms
4,852 KB |
ソースコード
#include <stdio.h> typedef struct List { struct List *next; int v, id; } list; int is_palindrome(char S[]) { int i, j; for (j = 0; S[j] != 0; j++); for (i = 0, j--; i < j; i++, j--) if (S[i] != S[j]) break; if (i < j) return 0; else return 1; } int is_unique(char S[]) { int i; for (i = 1; S[i] != 0; i++) if (S[i] != S[0]) break; if (S[i] != 0) return 0; else return 1; } int solve(int N, int M, list* adj[], char c[], int ans[]) { int i, j, k, u, w, par[2][100001] = {}, q[100001], head, tail; list *p; for (i = 2; i <= M; i++) if (c[i] != c[1]) break; if (i > M) return -1; par[0][N] = -N; q[0] = N; for (head = 0, tail = 1; head < tail; head++) { u = q[head]; for (p = adj[u]; p != NULL; p = p->next) { w = p->v; if (par[0][w] == 0) { par[0][w] = u; par[1][w] = p->id; q[tail++] = w; } } } if (par[0][1] == 0) return -1; char S[200001], T[200001]; for (u = 1, k = 0; u != N; u = -par[0][u], k++) { S[k] = c[par[1][u]]; ans[k] = par[1][u]; q[k] = u; par[0][u] *= -1; } S[k] = 0; if (is_palindrome(S) == 0) return k; else if (is_unique(S) == 0) { ans[k] = ans[k-1]; ans[k+1] = ans[k]; return k + 2; } q[k++] = N; for (u = 1; u < N; u++) if (par[0][u] > 0) par[0][u] = 0; for (head = 0, tail = k; head < tail; head++) { u = q[head]; for (p = adj[u]; p != NULL; p = p->next) { w = p->v; if (c[p->id] != S[0]) break; else if (par[0][w] == 0) { par[0][w] = u; par[1][w] = p->id; q[tail++] = w; } } if (p != NULL) break; } if (head == tail) return -1; int tmp[200001]; T[0] = c[p->id]; tmp[0] = p->id; for (j = 1; par[0][u] > 0; u = par[0][u], j++) { T[j] = c[par[1][u]]; tmp[j] = par[1][u]; } for (w = u, u = 1, k = 0; u != w; u = -par[0][u], k++) { S[k] = c[par[1][u]]; ans[k] = par[1][u]; } for (i = j - 1; i >= 0; i--, k++) { S[k] = T[i]; ans[k] = tmp[i]; } for (i = 0; i < j; i++, k++) { S[k] = T[i]; ans[k] = tmp[i]; } for (; u != N; u = -par[0][u], k++) { S[k] = c[par[1][u]]; ans[k] = par[1][u]; } S[k] = 0; if (is_palindrome(S) == 0) return k; else { ans[k] = ans[k-1]; ans[k+1] = ans[k]; return k + 2; } } int main() { int i, N, M, u, w; char c[200001]; list *adj[100001] = {}, e[400001]; scanf("%d %d", &N, &M); for (i = 0; i < M; i++) { scanf("%d %d %c ", &u, &w, &(c[i+1])); e[i*2].v = w; e[i*2+1].v = u; e[i*2].id = i + 1; e[i*2+1].id = i + 1; e[i*2].next = adj[u]; e[i*2+1].next = adj[w]; adj[u] = &(e[i*2]); adj[w] = &(e[i*2+1]); } int ans[200001], k = solve(N, M, adj, c, ans); printf("%d\n", k); if (k >= 0) for (i = 0; i < k; i++) printf("%d\n", ans[i]); fflush(stdout); return 0; }