結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー |
![]() |
提出日時 | 2021-08-13 22:30:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 252 ms / 2,500 ms |
コード長 | 2,358 bytes |
コンパイル時間 | 1,390 ms |
コンパイル使用メモリ | 124,552 KB |
最終ジャッジ日時 | 2025-01-23 20:09:45 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> #include <tuple> #include <cmath> #include <numeric> #include <functional> #include <cassert> #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; vector<int> g[200000]; bool used[200000]; int pre[200000]; vector<int> ans; void make_loop(int v, int end){ while(v != end){ ans.push_back(v); v = pre[v]; } ans.push_back(end); } bool dfs(int v){ used[v] = true; for(int to: g[v]){ if(!used[to]){ pre[to] = v; if(dfs(to)) return true; }else if(pre[v] != to){ make_loop(v, to); return true; } } return false; } using P = pair<int, int>; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int h, w; cin >> h >> w; int n; cin >> n; map<P, int> idx; vector<int> x(n), y(n); for(int i = 0; i < n; i++){ cin >> x[i] >> y[i]; x[i]--; y[i]--; g[x[i]].push_back(h+y[i]); g[h+y[i]].push_back(x[i]); idx[P(x[i], h+y[i])] = i; idx[P(h+y[i], x[i])] = i; } for(int i = 0; i < h+w; i++){ if(!used[i]){ if(dfs(i)){ int m = ans.size(); cout << m << endl; vector<int> v(m); for(int j = 0; j < m; j++){ int k = (j+1)%m; v[j] = idx[P(ans[j], ans[k])]; } if(x[v[0]] != x[v[1]]){ for(int j = 0; j < m; j++) cout << v[j]+1 << ' '; cout << endl; }else{ for(int j = 0; j < m; j++) cout << v[(j+1)%m]+1 << ' '; cout << endl; } // for(int j: v) cout << x[j] << ' ' << y[j] << endl; return 0; } } } cout << -1 << endl; }