結果
問題 | No.2565 はじめてのおつかい |
ユーザー | マベマス(mavemas_413) |
提出日時 | 2023-11-26 17:07:40 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 4,056 bytes |
コンパイル時間 | 6,071 ms |
コンパイル使用メモリ | 313,560 KB |
実行使用メモリ | 13,000 KB |
最終ジャッジ日時 | 2023-11-26 17:07:54 |
合計ジャッジ時間 | 12,035 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
9,876 KB |
testcase_01 | AC | 6 ms
9,876 KB |
testcase_02 | AC | 7 ms
9,876 KB |
testcase_03 | AC | 103 ms
13,000 KB |
testcase_04 | AC | 76 ms
13,000 KB |
testcase_05 | AC | 6 ms
9,876 KB |
testcase_06 | AC | 63 ms
11,184 KB |
testcase_07 | AC | 35 ms
10,604 KB |
testcase_08 | AC | 35 ms
10,540 KB |
testcase_09 | AC | 67 ms
11,056 KB |
testcase_10 | AC | 41 ms
10,676 KB |
testcase_11 | AC | 82 ms
11,660 KB |
testcase_12 | AC | 25 ms
10,392 KB |
testcase_13 | AC | 41 ms
10,680 KB |
testcase_14 | AC | 63 ms
11,160 KB |
testcase_15 | AC | 69 ms
11,244 KB |
testcase_16 | AC | 55 ms
11,600 KB |
testcase_17 | AC | 16 ms
10,224 KB |
testcase_18 | AC | 19 ms
10,396 KB |
testcase_19 | AC | 67 ms
11,548 KB |
testcase_20 | AC | 59 ms
11,348 KB |
testcase_21 | AC | 59 ms
11,348 KB |
testcase_22 | AC | 35 ms
10,752 KB |
testcase_23 | AC | 40 ms
10,840 KB |
testcase_24 | AC | 12 ms
10,060 KB |
testcase_25 | AC | 60 ms
11,332 KB |
testcase_26 | AC | 40 ms
10,816 KB |
testcase_27 | AC | 70 ms
11,368 KB |
testcase_28 | AC | 66 ms
11,532 KB |
testcase_29 | AC | 73 ms
11,768 KB |
testcase_30 | AC | 61 ms
11,500 KB |
testcase_31 | AC | 62 ms
11,408 KB |
testcase_32 | AC | 35 ms
10,744 KB |
testcase_33 | AC | 58 ms
11,420 KB |
testcase_34 | AC | 62 ms
11,376 KB |
testcase_35 | AC | 60 ms
11,600 KB |
testcase_36 | AC | 61 ms
11,432 KB |
testcase_37 | AC | 39 ms
10,804 KB |
testcase_38 | AC | 59 ms
11,352 KB |
testcase_39 | AC | 55 ms
11,112 KB |
testcase_40 | AC | 69 ms
11,724 KB |
testcase_41 | AC | 71 ms
11,808 KB |
testcase_42 | AC | 41 ms
10,832 KB |
testcase_43 | AC | 53 ms
11,208 KB |
testcase_44 | AC | 36 ms
10,580 KB |
testcase_45 | AC | 19 ms
10,268 KB |
testcase_46 | AC | 73 ms
11,352 KB |
testcase_47 | AC | 50 ms
10,936 KB |
testcase_48 | AC | 42 ms
10,704 KB |
testcase_49 | AC | 25 ms
10,376 KB |
testcase_50 | AC | 59 ms
11,148 KB |
testcase_51 | AC | 7 ms
9,876 KB |
testcase_52 | AC | 47 ms
11,148 KB |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; // long long using ll = long long; // unsigned long long using ull = unsigned long long; // string using str = string; // long double using ld = long double; // pair using pll = pair < ll, ll >; // tuple using tlll = tuple < ll, ll, ll >; // vector template < class T > using v = vector < T >; using vl = v < ll >; using vbl = v < bool >; // priority_queue template < class T > using pq = priority_queue < T >; template < class T > using pqg = priority_queue < T, v < T >, greater < T > >; // unordered_set template < class T > using uset = unordered_set < T > ; // unordered_map template < class T, class U > using umap = unordered_map < T, U > ; // rep #define rep(i, a, b) for(ll i = a; i <= b; i ++) #define Rep(i, a) for(ll i = 0; i < a; i ++) #define rrep(i, a, b) for(ll i = a; i >= b; i --) #define repp(i, a, b, c) for(ll i = a; i <= b; i += c) // binary search #define lobo(x, k) lower_bound(x.begin(), x.end(), k) - x.begin() #define Lobo(x, a, b, k) lower_bound(x + a, x + b + 1, k) - x #define upbo(x, k) upper_bound(x.begin(), x.end(), k) - x.begin() #define Upbo(x, a, b, k) upper_bound(x + a, x + b + 1, k) - x; // snippet #define eruni(x) x.erase(unique(x.begin(), x.end()), x.end()) #define eb emplace_back #define mp make_pair #define mt make_tuple #define all(x) x.begin(), x.end() #define rll(x) x.rbegin(), x.rend() #define sz(x) (ll)x.size() #define f first #define s second #define in insert #define pf push_front #define p_f pop_front #define pb push_back #define p_b pop_back #define p_p prev_permutation #define n_p next_permutation #define led leader #define print(a) printf("%.20Lf", a) #define func function // function template < class T > bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;} template < class T > bool chmin(T &a, const T &b) {if (b < a) {a = b; return 1;} return 0;} // out void Yes(bool f = true) {cout << (f ? "Yes" : "No" ) << endl;} void No(bool f = true) {cout << (f ? "No" : "Yes" ) << endl;} void YES(bool f = true) {cout << (f ? "YES" : "NO" ) << endl;} void NO(bool f = true) {cout << (f ? "NO" : "YES" ) << endl;} template < class T > void out(T a) {cout << a << endl;} template < class T > void out1(T a) {cout << a << " ";} template < class T, class U > void out2(T a, U b) {cout << a << " " << b << endl;} template < class T> void allout(T &a) { for(auto x : a) cout << x << " "; cout << endl; } template < class T > void allout1(T &a) { for(auto x : a) cout << x << endl; } // modint using modi = modint998244353; using mint = modint1000000007; // constant const ll md = 998244353; const ll mo = 1000000007; const ld pi = acos(-1); const ll inf = (1LL << 60); const ll n1 = 100009; const ll n2 = 200009; const ll n3 = 300009; const ll n5 = 500009; // grid const pll ar1[4] = { {0, 0}, {1, 0}, {0, 1}, {1, 1} }; const pll ar2[4] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} }; const pll ar3[8] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1}, {-1, 1}, {1, -1}, {1, 1}, {-1, -1} }; int main(){ ll n, m; vl G[n2]; cin >> n >> m; Rep(i, m){ ll a, b; cin >> a >> b; G[a].eb(b); } auto bfs = [&](ll x, ll y){ vl D(n2, -1); queue < ll > Q; Q.push(x); D[x] = 0; while(sz(Q)){ ll p = Q.front(); Q.pop(); for(auto nex : G[p]){ if(D[nex] == -1){ D[nex] = D[p] + 1; Q.push(nex); } } } return D[y]; }; ll d1 = -1, d2 = -1, ans = inf; bool f1 = true, f2 = true; if(bfs(1, n - 1) == -1 || bfs(n - 1, n) == -1 || bfs(n, 1) == -1) f1 = false; if(bfs(1, n) == -1 || bfs(n, n - 1) == -1 || bfs(n - 1, 1) == -1) f2 = false; if(f1){ d1 ++; d1 += bfs(1, n - 1); d1 += bfs(n - 1, n); d1 += bfs(n, 1); chmin(ans, d1); } if(f2){ d2 ++; d2 += bfs(1, n); d2 += bfs(n, n - 1); d2 += bfs(n - 1, 1); chmin(ans, d2); } if(ans == inf) ans = -1; out(ans); }