結果
問題 | No.1612 I hate Construct a Palindrome |
ユーザー |
![]() |
提出日時 | 2021-07-21 22:11:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 403 ms / 2,000 ms |
コード長 | 2,057 bytes |
コンパイル時間 | 2,045 ms |
コンパイル使用メモリ | 189,464 KB |
実行使用メモリ | 58,928 KB |
最終ジャッジ日時 | 2024-07-17 18:54:09 |
合計ジャッジ時間 | 7,415 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N, M; cin >> N >> M; vector<vector<tuple<char, int, int>>> E(N); for (int i = 0; i < M; i++){ int A, B; char C; cin >> A >> B >> C; A--; B--; E[A].push_back(make_tuple(C, i, B)); E[B].push_back(make_tuple(C, i, A)); } vector<vector<int>> d(27, vector<int>(N, -1)); vector<vector<int>> pv(27, vector<int>(N, -1)); vector<vector<int>> pe(27, vector<int>(N, -1)); vector<vector<int>> ps(27, vector<int>(N, -1)); vector<vector<char>> pc(27, vector<char>(N, -1)); queue<pair<int, int>> Q; for (auto e : E[0]){ char c = get<0>(e); int w = get<2>(e); int s = c - 'a'; d[s][w] = 1; pv[s][w] = 0; pe[s][w] = get<1>(e); ps[s][w] = s; pc[s][w] = c; Q.push(make_pair(s, w)); } while (!Q.empty()){ int s = Q.front().first; int v = Q.front().second; Q.pop(); for (auto e : E[v]){ char c = get<0>(e); int w = get<2>(e); int s2 = s; if (s != c - 'a'){ s2 = 26; } if (d[s2][w] == -1){ d[s2][w] = d[s][v] + 1; pv[s2][w] = v; pe[s2][w] = get<1>(e); ps[s2][w] = s; pc[s2][w] = c; Q.push(make_pair(s2, w)); } } } if (d[26][N - 1] == -1){ cout << -1 << endl; } else { string S; vector<int> ans; int c = N - 1; int s = 26; while (true){ S += pc[s][c]; ans.push_back(pe[s][c]); if (d[s][c] == 1){ break; } int c2 = pv[s][c]; int s2 = ps[s][c]; c = c2; s = s2; } reverse(S.begin(), S.end()); reverse(ans.begin(), ans.end()); string S2 = S; reverse(S2.begin(), S2.end()); if (S == S2){ char ch = pc[26][N - 1]; S += ch; S += ch; ans.push_back(pe[26][N - 1]); ans.push_back(pe[26][N - 1]); S2 = S; reverse(S2.begin(), S2.end()); } int k = ans.size(); cout << k << endl; for (int i = 0; i < k; i++){ cout << ans[i] + 1 << endl; } } }