結果

問題 No.1647 Travel in Mitaru city 2
ユーザー startcppstartcpp
提出日時 2021-08-13 22:57:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,894 bytes
コンパイル時間 1,052 ms
コンパイル使用メモリ 96,916 KB
実行使用メモリ 30,268 KB
最終ジャッジ日時 2024-10-03 22:03:03
合計ジャッジ時間 14,728 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 32
権限があれば一括ダウンロードができます

ソースコード

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