結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
8,220 KB
testcase_01 AC 4 ms
7,996 KB
testcase_02 AC 5 ms
8,192 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 246 ms
29,420 KB
testcase_23 AC 247 ms
29,632 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 243 ms
29,632 KB
testcase_27 AC 245 ms
29,896 KB
testcase_28 AC 245 ms
30,528 KB
testcase_29 AC 248 ms
30,524 KB
testcase_30 WA -
testcase_31 AC 250 ms
30,656 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 234 ms
30,524 KB
testcase_35 AC 217 ms
27,576 KB
testcase_36 AC 247 ms
30,656 KB
testcase_37 AC 237 ms
30,656 KB
testcase_38 AC 218 ms
25,072 KB
testcase_39 WA -
testcase_40 AC 216 ms
24,704 KB
testcase_41 WA -
testcase_42 WA -
testcase_43 AC 5 ms
8,192 KB
testcase_44 AC 4 ms
8,192 KB
testcase_45 WA -
testcase_46 AC 1,124 ms
18,432 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;
}

void rotation(vector<int> &vec) {
	vector<int> nv;
	for (int i = 0; i < vec.size(); i++) {
		nv.push_back(vec[(i + 1) % vec.size()]);
	}
	vec = nv;
}

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--;
	}
	
	//pathは --->(loop)の形をしているので、loopだけを切り出す
	int i;
	for (i = 1; i < vs.size(); i++) {
		if (vs[i] == vs[0]) {
			break;
		}
	}
	if (i == vs.size()) i = 0;
	
	vector<int> cycle;
	for (; i < vs.size(); i++) {
		cycle.push_back(vs[i]);
	}
	
	if (cycle[0] >= h) {
		rotation(cycle);
	}
	
	vs = cycle;
	
	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 + w) {
		if (visit[i]) continue;
		if (dfs(-1, i, path)) {
			vector<int> ans = makeAnswer(path);
			printAnswer(ans);
			return 0;
		}
	}
	
	cout << -1 << endl;
	return 0;
}
0