結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー | keijak |
提出日時 | 2021-08-21 08:34:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,217 bytes |
コンパイル時間 | 3,058 ms |
コンパイル使用メモリ | 214,948 KB |
実行使用メモリ | 46,464 KB |
最終ジャッジ日時 | 2024-04-22 18:16:05 |
合計ジャッジ時間 | 16,881 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,624 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 4 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 5 ms
5,376 KB |
testcase_08 | AC | 203 ms
42,752 KB |
testcase_09 | AC | 170 ms
39,488 KB |
testcase_10 | AC | 200 ms
43,136 KB |
testcase_11 | AC | 106 ms
30,604 KB |
testcase_12 | AC | 175 ms
40,704 KB |
testcase_13 | AC | 188 ms
41,984 KB |
testcase_14 | AC | 198 ms
44,096 KB |
testcase_15 | AC | 200 ms
43,756 KB |
testcase_16 | AC | 188 ms
41,088 KB |
testcase_17 | AC | 171 ms
40,176 KB |
testcase_18 | AC | 157 ms
38,912 KB |
testcase_19 | AC | 182 ms
43,008 KB |
testcase_20 | AC | 173 ms
42,156 KB |
testcase_21 | AC | 184 ms
43,440 KB |
testcase_22 | AC | 205 ms
44,896 KB |
testcase_23 | AC | 209 ms
45,312 KB |
testcase_24 | AC | 151 ms
37,816 KB |
testcase_25 | AC | 126 ms
34,944 KB |
testcase_26 | AC | 214 ms
45,184 KB |
testcase_27 | AC | 220 ms
45,364 KB |
testcase_28 | AC | 213 ms
46,456 KB |
testcase_29 | AC | 219 ms
46,464 KB |
testcase_30 | AC | 186 ms
42,880 KB |
testcase_31 | AC | 212 ms
46,284 KB |
testcase_32 | AC | 164 ms
40,192 KB |
testcase_33 | AC | 152 ms
39,400 KB |
testcase_34 | AC | 214 ms
46,336 KB |
testcase_35 | AC | 181 ms
42,848 KB |
testcase_36 | AC | 213 ms
46,464 KB |
testcase_37 | AC | 215 ms
46,456 KB |
testcase_38 | AC | 180 ms
39,680 KB |
testcase_39 | AC | 210 ms
37,504 KB |
testcase_40 | AC | 181 ms
39,420 KB |
testcase_41 | AC | 153 ms
37,248 KB |
testcase_42 | AC | 180 ms
39,424 KB |
testcase_43 | AC | 3 ms
5,376 KB |
testcase_44 | AC | 6 ms
7,808 KB |
testcase_45 | AC | 92 ms
30,940 KB |
testcase_46 | TLE | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
testcase_50 | -- | - |
ソースコード
#include <bits/stdc++.h> #define REP_(i, a_, b_, a, b, ...) \ for (int i = (a), END_##i = (b); i < END_##i; ++i) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define ALL(x) std::begin(x), std::end(x) using i64 = long long; template<typename T, typename U> inline bool chmax(T &a, U b) { return a < b and ((a = std::move(b)), true); } template<typename T, typename U> inline bool chmin(T &a, U b) { return a > b and ((a = std::move(b)), true); } template<typename T> inline int ssize(const T &a) { return (int) std::size(a); } template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &a) { for (auto &x : a) is >> x; return is; } template<typename T, typename U> std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &a) { return os << "(" << a.first << ", " << a.second << ")"; } template<typename Container> std::ostream &print_seq(const Container &a, std::string_view sep = " ", std::string_view ends = "\n", std::ostream &os = std::cout) { auto b = std::begin(a), e = std::end(a); for (auto it = std::begin(a); it != e; ++it) { if (it != b) os << sep; os << *it; } return os << ends; } template<typename T, typename = void> struct is_iterable : std::false_type {}; template<typename T> struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>())), decltype(std::end(std::declval<T>()))>> : std::true_type { }; template<typename T, typename = std::enable_if_t< is_iterable<T>::value && !std::is_same<T, std::string_view>::value && !std::is_same<T, std::string>::value>> std::ostream &operator<<(std::ostream &os, const T &a) { return print_seq(a, ", ", "", (os << "{")) << "}"; } void print() { std::cout << "\n"; } template<class T> void print(const T &x) { std::cout << x << "\n"; } template<typename Head, typename... Tail> void print(const Head &head, Tail... tail) { std::cout << head << " "; print(tail...); } void read_from_cin() {} template<typename T, typename... Ts> void read_from_cin(T &value, Ts &...args) { std::cin >> value; read_from_cin(args...); } #define INPUT(type, ...) \ type __VA_ARGS__; \ read_from_cin(__VA_ARGS__) #ifdef MY_DEBUG #include "debug_dump.hpp" #else #define DUMP(...) #endif using namespace std; auto solve() -> optional<vector<int>> { INPUT(i64, H, W, n); vector<pair<int, int>> spots(n); vector<vector<int>> rows(H), cols(W); REP(i, n) { INPUT(int, x, y); --x, --y; spots[i] = {x, y}; rows[x].push_back(i); cols[y].push_back(i); } auto par = vector(n, vector(2, -1)); auto done = vector(n, vector(2, false)); auto depth = vector(n, vector(2, -1)); vector<int> anc(n, -1); auto dfs = [&](auto &dfs, int v, int j) -> optional<vector<int>> { int x, y; tie(x, y) = spots[v]; vector<int> &nexts = (j & 1) ? rows[x] : cols[y]; for (int u : nexts) { if (anc[u] != -1) { if (anc[u] == j) continue; if (depth[v][j] - depth[u][1 - j] < 3) continue; vector<int> path; for (int w = v, p = j; w != -1; w = par[w][p], p ^= 1) { path.push_back(w); if (w == u) break; } reverse(ALL(path)); if (j == 0) { std::rotate(path.begin(), path.begin() + 1, path.end()); } return path; } done[u][1 - j] = true; depth[u][1 - j] = depth[v][j] + 1; par[u][1 - j] = v; anc[u] = 1 - j; auto sub = dfs(dfs, u, 1 - j); if (sub) return sub; anc[u] = -1; } return nullopt; }; REP(i, 2) { REP(v, n) { if (done[v][i]) continue; done[v][i] = true; depth[v][i] = i; anc[v] = i; auto sub = dfs(dfs, v, i); if (sub) return sub; anc[v] = -1; } } return nullopt; } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); cout << std::fixed << std::setprecision(15); int t = 1; REP(test_case, t) { auto ans = solve(); if (not ans) { print(-1); } else { auto &v = ans.value(); print(v.size()); for (auto &x : v) ++x; print_seq(v); } } }