結果
| 問題 | No.1612 I hate Construct a Palindrome |
| ユーザー |
 momoyuu
|
| 提出日時 | 2024-08-09 18:41:30 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,460 bytes |
| コンパイル時間 | 2,502 ms |
| コンパイル使用メモリ | 141,252 KB |
| 実行使用メモリ | 18,432 KB |
| 最終ジャッジ日時 | 2024-08-09 18:41:40 |
| 合計ジャッジ時間 | 9,768 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 9 WA * 27 |
コンパイルメッセージ
In lambda function,
inlined from 'std::vector<int> solve2()' at main.cpp:186:8:
main.cpp:162:9: warning: 'wv' may be used uninitialized [-Wmaybe-uninitialized]
162 | if(ni==to){
| ^~
main.cpp: In function 'std::vector<int> solve2()':
main.cpp:145:9: note: 'wv' was declared here
145 | int wv;
| ^~
In lambda function,
inlined from 'std::vector<int> solve2()' at main.cpp:175:8:
main.cpp:170:16: warning: 'wu' may be used uninitialized [-Wmaybe-uninitialized]
170 | dfs(dfs,nj,to);
| ~~~^~~~~~~~~~~
main.cpp: In function 'std::vector<int> solve2()':
main.cpp:143:9: note: 'wu' was declared here
143 | int wu,ni;
| ^~
main.cpp: In function 'std::vector<int> solve1()':
main.cpp:108:30: warning: 'nj' may be used uninitialized [-Wmaybe-uninitialized]
108 | ans.push_back(g[0][nj].second.second);
| ^
main.cpp:100:13: note: 'nj' was declared here
100 | int nj;
| ^~
main.cpp:114:29: warning: 'wu' may be used uninitialized [-Wmaybe-uninitialized]
114 | for(int i = 0;i<g[wu].size();i++){
| ^
main.cpp:64:9: note: 'wu' was declared here
64 | int wu,ni;
| ^~
main.cpp:23:30: warning: 'nj' may be used uninitialized [-Wmaybe-uninitialized]
23 | ans.push_back(g[0][nj].second.second);
| ^
main.cpp:15:20: note: 'nj' was declared here
15 | int ni = 0,nj;
| ^~
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;using ll = long long;#include<set>#include<cassert>int n,m;vector<vector<pair<int,pair<char,int>>>> g;vector<char> C;vector<int> solve1(){if(n==2){int ni = 0,nj;for(int i = 0;i<g[0].size();i++){if(g[0][0].second.first==g[0][i].second.first) continue;nj = i;break;}vector<int> ans;ans.push_back(g[0][0].second.second);ans.push_back(g[0][nj].second.second);ans.push_back(g[0][nj].second.second);return ans;}else if(n==3){vector<int> ans;for(int i = 0;i<3;i++){set<int> a;set<char> b;vector<int> use;for(int j = 0;j<g[i].size();j++){if(b.find(g[i][j].second.first)!=b.end()) continue;if(a.find(g[i][j].first)!=a.end()) continue;b.insert(g[i][j].second.first);a.insert(g[i][j].first);use.push_back(j);}if(a.size()<2) continue;int ni = use[0];int nj = use[1];if(i==0){if(g[0][ni].first==2) swap(ni,nj);ans.push_back(g[0][ni].second.second);ans.push_back(g[0][ni].second.second);ans.push_back(g[0][nj].second.second);break;}else if(i==1){if(g[i][ni].first==2) swap(ni,nj);ans.push_back(g[0][ni].second.second);ans.push_back(g[0][nj].second.second);break;}else{if(g[i][ni].first==1) swap(ni,nj);ans.push_back(g[0][ni].second.second);ans.push_back(g[0][nj].second.second);ans.push_back(g[0][nj].second.second);break;}}return ans;}char no = g[n-1][0].second.first;int wu,ni;ni = -1;int wv;for(int i = 0;i<n;i++){set<char> now;for(auto itr:g[i]){now.insert(itr.second.first);}if(now.size()==1) continue;wu = i;break;}vector<int> vis(n,0);bool fn = false;vector<int> que;auto dfs = [&](auto dfs,int ni,int to) -> void {vis[ni]++;if(ni==to){fn = true;return;}for(auto&itr:g[ni]){int nj = itr.first;if(vis[nj]) continue;que.push_back(itr.second.second);dfs(dfs,nj,to);if(fn) return;que.pop_back();}};dfs(dfs,0,wu);vector<int> ans = que;que.clear();int k = wu;if(wu==0){int ni = 0;int nj;for(int j = 1;j<g[0].size();j++){if(g[0][j].second.first!=g[0][0].second.first){nj = j;break;}}ans.push_back(g[0][ni].second.second);ans.push_back(g[0][nj].second.second);ans.push_back(g[0][nj].second.second);k = g[0][nj].first;}else{assert(!ans.empty());int ni = ans.back();for(int i = 0;i<g[wu].size();i++){if(g[wu][i].second.first==C[ni]) continue;ans.push_back(g[wu][i].second.second);k = g[wu][i].first;break;}}for(int i = 0;i<n;i++) vis[i] = 0;int from = k;int to = n - 1;fn = false;dfs(dfs,from,to);for(int i:que) ans.push_back(i);string use;for(int i = 0;i<ans.size();i++){use += C[ans[i]-1];}string u = use;reverse(u.begin(),u.end());if(use==u){ans.push_back(g[n-1][0].second.second);ans.push_back(g[n-1][0].second.second);}return ans;}vector<int> solve2(){char no = g[n-1][0].second.first;int wu,ni;ni = -1;int wv;for(int i = 0;i<n;i++){for(auto itr:g[i]){if(itr.second.first==no) continue;wu = i;wv = itr.first;ni = itr.second.second;break;}if(ni!=-1) break;}vector<int> vis(n,0);bool fn = false;vector<int> que;auto dfs = [&](auto dfs,int ni,int to) -> void {vis[ni]++;if(ni==to){fn = true;return;}for(auto&itr:g[ni]){int nj = itr.first;if(vis[nj]) continue;que.push_back(itr.second.second);dfs(dfs,nj,to);if(fn) return;que.pop_back();}};dfs(dfs,0,wu);vector<int> ans = que;int cnt = ans.size();que.clear();for(int i = 0;i<n;i++) vis[i] = 0;int from = wv;ans.push_back(ni);int to = n - 1;cnt++;if(cnt%2==1) to = g[n-1][0].first;fn = false;dfs(dfs,from,to);for(int i:que) ans.push_back(i);for(int i = 0;i<cnt;i++){ans.push_back(g[n-1][0].second.second);if(to==n-1) {to = g[n-1][0].first;}else{to = n-1;}}return ans;}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);set<char> s;cin>>n>>m;g.resize(n);C.resize(m);vector<int> uu(m),vv(m);for(int i = 0;i<m;i++){int u,v;char c;cin>>u>>v>>c;C[i] = c;u--;v--;s.insert(c);g[u].push_back({v,{c,i+1}});g[v].push_back({u,{c,i+1}});uu[i] = u;vv[i] = v;}if(s.size()==1){cout<<-1<<endl;return 0;}auto ans = solve1();{int ni = 0;bool fn = true;string now;for(int i:ans) now += C[i];for(int i:ans){if(fn&&uu[i]!=ni&&vv[i]!=ni) fn = false;ni = uu[i] + vv[i] - ni;}string t = now;reverse(now.begin(),now.end());if(ans.size()<=2*n&&now!=t){cout<<ans.size()<<endl;for(int i:ans) cout<<i<<endl;return 0;}}ans = solve2();{string now;for(int i:ans) now += C[i];string t = now;reverse(now.begin(),now.end());if(ans.size()<=2*n&&now!=t){cout<<ans.size()<<endl;for(int i:ans) cout<<i<<endl;return 0;}}}