結果
問題 |
No.1647 Travel in Mitaru city 2
|
ユーザー |
|
提出日時 | 2021-08-13 21:53:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 166 ms / 2,500 ms |
コード長 | 1,032 bytes |
コンパイル時間 | 832 ms |
コンパイル使用メモリ | 75,652 KB |
実行使用メモリ | 41,948 KB |
最終ジャッジ日時 | 2024-10-13 03:14:52 |
合計ジャッジ時間 | 9,428 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
コンパイルメッセージ
main.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 30 | main() | ^~~~
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; int H,W,N; int X[1<<17],Y[1<<17]; vector<int>G[3<<17]; vector<int>tmp; vector<int>ans; int vis[3<<17]; bool dfs(int u,int p) { vis[u]=tmp.size(); tmp.push_back(u); for(int v:G[u])if(v!=p) { if(vis[v]==-1) { if(dfs(v,u))return true; } else { ans=vector<int>(tmp.begin()+vis[v],tmp.end()); return true; } } tmp.pop_back(); return false; } main() { cin>>H>>W>>N; for(int i=0;i<N;i++) { cin>>X[i]>>Y[i]; X[i]--,Y[i]--; G[i].push_back(N+X[i]); G[i].push_back(N+H+Y[i]); G[N+X[i]].push_back(i); G[N+H+Y[i]].push_back(i); } for(int i=0;i<N+H+W;i++)vis[i]=-1; for(int i=0;i<N;i++)if(vis[i]==-1) { if(dfs(i,-1)) { vector<int>ret; for(int id:ans)if(id<N)ret.push_back(id); if(X[ret[0]]==X[ret[1]]) { ret.push_back(ret[0]); ret.erase(ret.begin()); } cout<<ret.size()<<endl; for(int i=0;i<ret.size();i++)cout<<ret[i]+1<<(i+1==ret.size()?"\n":" "); return 0; } } cout<<-1<<endl; }