結果

問題 No.1647 Travel in Mitaru city 2
ユーザー startcppstartcpp
提出日時 2021-08-13 22:57:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,894 bytes
コンパイル時間 1,199 ms
コンパイル使用メモリ 96,924 KB
実行使用メモリ 30,276 KB
最終ジャッジ日時 2024-04-14 19:50:57
合計ジャッジ時間 17,034 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
8,168 KB
testcase_01 AC 4 ms
8,204 KB
testcase_02 AC 5 ms
8,244 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 237 ms
28,908 KB
testcase_23 AC 235 ms
29,240 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 226 ms
29,240 KB
testcase_27 AC 238 ms
29,452 KB
testcase_28 AC 241 ms
30,148 KB
testcase_29 AC 233 ms
30,140 KB
testcase_30 WA -
testcase_31 AC 236 ms
30,140 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 240 ms
30,276 KB
testcase_35 AC 221 ms
27,312 KB
testcase_36 AC 230 ms
30,276 KB
testcase_37 AC 237 ms
30,144 KB
testcase_38 AC 216 ms
24,848 KB
testcase_39 WA -
testcase_40 AC 218 ms
24,452 KB
testcase_41 WA -
testcase_42 WA -
testcase_43 AC 3 ms
8,304 KB
testcase_44 AC 4 ms
8,400 KB
testcase_45 WA -
testcase_46 AC 617 ms
18,592 KB
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

//行: 0～h-1, 列:0～w-1で頂点を持つ一般的なテク. 閉路検出.
#include <iostream>
#include <stack>
#include <map>
#include <vector>
#include <algorithm>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
typedef pair<int, int> P;

int h, w, n;
vector<int> et[200000];	//行き先
vector<bool> visit;
map<P, int> toId;

bool dfs(int pv, int v, stack<int> &path) {
	visit[v] = true;
	path.push(v);
	for (int i = 0; i < et[v].size(); i++) {
		int nv = et[v][i];
		if (pv == nv) continue;
		if (visit[nv]) {
			if (path.size() >= 4) {
				return true;
			}
			continue;
		}
		else {
			if (dfs(v, nv, path)) return true;
		}
	}
	visit[v] = false;
	path.pop();
	return false;
}

vector<int> makeAnswer(stack<int> path) {
	vector<int> vs;
	while (!path.empty()) {
		int v = path.top(); path.pop();
		vs.push_back(v);
	}
	
	int l = 0, r = vs.size() - 1;
	while (l < r) {
		swap(vs[l], vs[r]);
		l++; r--;
	}
	
	vector<int> ans;
	for (int i = 0; i < vs.size(); i++) {
		int r, c;
		if (i + 1 == vs.size()) {
			if (vs[i] < h) { r = vs[i]; c = vs[0] - h; }
			else { c = vs[i] - h; r = vs[0]; }
		}
		else {
			if (vs[i] < h) { r = vs[i]; c = vs[i + 1] - h; }
			else { c = vs[i] - h; r = vs[i + 1]; }
		}
		int id = toId[P(r, c)];
		ans.push_back(id);
	}
	return ans;
}

void printAnswer(vector<int> ans) {
	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] + 1;
		if (i + 1 < ans.size()) cout << " ";
	}
	cout << endl;
}

signed main() {
	int i;
	
	cin >> h >> w >> n;
	rep(i, n) {
		int r, c;
		cin >> r >> c;
		r--; c--;
		et[r].push_back(c + w);
		et[c + h].push_back(r);
		toId[P(r, c)] = i;
	}
	
	visit = vector<bool>(h + w, false);
	
	stack<int> path;
	rep(i, h) {
		if (visit[i]) continue;
		if (dfs(-1, i, path)) {
			vector<int> ans = makeAnswer(path);
			printAnswer(ans);
			return 0;
		}
	}
	
	cout << -1 << endl;
	return 0;
}
0