結果
| 問題 | No.1612 I hate Construct a Palindrome |
| ユーザー |
 momoyuu
|
| 提出日時 | 2024-08-09 18:32:31 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,330 bytes |
| コンパイル時間 | 1,651 ms |
| コンパイル使用メモリ | 128,404 KB |
| 実行使用メモリ | 23,688 KB |
| 最終ジャッジ日時 | 2024-08-09 18:32:41 |
| 合計ジャッジ時間 | 9,585 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 10 WA * 25 RE * 1 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:126:30: warning: 'nj' may be used uninitialized [-Wmaybe-uninitialized]
126 | ans.push_back(g[0][nj].second.second);
| ^
main.cpp:118:13: note: 'nj' was declared here
118 | int nj;
| ^~
main.cpp:131:29: warning: 'wu' may be used uninitialized [-Wmaybe-uninitialized]
131 | for(int i = 0;i<g[wu].size();i++){
| ^
main.cpp:82:9: note: 'wu' was declared here
82 | int wu,ni;
| ^~
main.cpp:40:51: warning: 'nj' may be used uninitialized [-Wmaybe-uninitialized]
40 | cout<<g[0][0].second.second<<endl<<g[0][nj].second.second<<endl<<g[0][nj].second.second<<endl;
| ^
main.cpp:33:20: note: 'nj' was declared here
33 | int ni = 0,nj;
| ^~
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;using ll = long long;#include<set>int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n,m;cin>>n>>m;vector<vector<pair<int,pair<char,int>>>> g(n);vector<char> C(m);set<char> s;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}});}if(s.size()==1){cout<<-1<<endl;return 0;}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;}cout<<3<<endl;cout<<g[0][0].second.second<<endl<<g[0][nj].second.second<<endl<<g[0][nj].second.second<<endl;return 0;}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;}}cout<<ans.size()<<endl;for(int i = 0;i<ans.size();i++) cout<<ans[i]<<endl;return 0;}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].second.second;}else{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);}cout<<ans.size()<<endl;for(int i = 0;i<ans.size();i++) cout<<ans[i]<<endl;}