結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー |
![]() |
提出日時 | 2021-08-13 21:38:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,500 ms |
コード長 | 1,600 bytes |
コンパイル時間 | 1,658 ms |
コンパイル使用メモリ | 178,532 KB |
実行使用メモリ | 24,308 KB |
最終ジャッジ日時 | 2024-10-13 03:13:19 |
合計ジャッジ時間 | 8,838 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
#include <bits/stdc++.h>using namespace std;void dfs(vector<vector<pair<int, int>>> &E, vector<int> &d, vector<int> &p, vector<int> &p2, int v){for (auto P : E[v]){int w = P.first;int id = P.second;if (d[w] == -1){d[w] = d[v] + 1;p[w] = v;p2[w] = id;dfs(E, d, p, p2, w);}}}int main(){int H, W, N;cin >> H >> W >> N;vector<int> x(N), y(N);for (int i = 0; i < N; i++){cin >> x[i] >> y[i];x[i]--;y[i]--;}vector<vector<pair<int, int>>> E(H + W);for (int i = 0; i < N; i++){E[x[i]].push_back(make_pair(H + y[i], i));E[H + y[i]].push_back(make_pair(x[i], i));}vector<int> d(H + W, -1);vector<int> p(H + W, -1);vector<int> p2(H + W, -1);for (int i = 0; i < H + W; i++){if (d[i] == -1){d[i] = 0;dfs(E, d, p, p2, i);}}vector<int> T;for (int i = 0; i < H + W; i++){for (auto P : E[i]){int w = P.first;int id = P.second;if (i != p[w] && w != p[i]){int a = i, b = w;if (d[b] < d[a]){swap(a, b);}T.push_back(id);for (int v = b; v != a; v = p[v]){T.push_back(p2[v]);}break;}}if (!T.empty()){break;}}if (T.empty()){cout << -1 << endl;} else {if (y[T[0]] != y[T[1]]){rotate(T.begin(), T.begin() + 1, T.end());}int X = T.size();cout << X << endl;for (int i = 0; i < X; i++){cout << T[i] + 1;if (i < X - 1){cout << ' ';}}cout << endl;}}