結果
問題 | No.1190 Points |
ユーザー | yukudo |
提出日時 | 2020-08-31 04:42:44 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 2,142 bytes |
コンパイル時間 | 1,760 ms |
コンパイル使用メモリ | 176,256 KB |
実行使用メモリ | 11,480 KB |
最終ジャッジ日時 | 2024-04-27 13:59:13 |
合計ジャッジ時間 | 4,463 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
8,024 KB |
testcase_01 | AC | 4 ms
7,828 KB |
testcase_02 | AC | 4 ms
8,132 KB |
testcase_03 | AC | 42 ms
10,468 KB |
testcase_04 | AC | 36 ms
10,012 KB |
testcase_05 | AC | 36 ms
9,992 KB |
testcase_06 | AC | 50 ms
10,904 KB |
testcase_07 | AC | 59 ms
11,288 KB |
testcase_08 | AC | 57 ms
11,424 KB |
testcase_09 | AC | 60 ms
11,192 KB |
testcase_10 | AC | 58 ms
11,480 KB |
testcase_11 | AC | 45 ms
10,140 KB |
testcase_12 | AC | 57 ms
11,412 KB |
testcase_13 | AC | 45 ms
10,036 KB |
testcase_14 | AC | 15 ms
9,156 KB |
testcase_15 | AC | 69 ms
11,260 KB |
testcase_16 | AC | 10 ms
8,508 KB |
testcase_17 | AC | 61 ms
10,900 KB |
testcase_18 | AC | 37 ms
9,592 KB |
testcase_19 | AC | 11 ms
8,648 KB |
testcase_20 | AC | 43 ms
9,948 KB |
testcase_21 | AC | 19 ms
9,104 KB |
testcase_22 | AC | 24 ms
9,892 KB |
testcase_23 | AC | 66 ms
11,128 KB |
testcase_24 | AC | 77 ms
11,260 KB |
testcase_25 | AC | 54 ms
11,136 KB |
testcase_26 | AC | 49 ms
10,636 KB |
testcase_27 | AC | 57 ms
11,016 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i) #define ALL(v) (v).begin(),(v).end() #define CLR(t,v) memset(t,(v),sizeof(t)) template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";} template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;} template<class T>void chmin(T&a,const T&b){if(a>b)a=b;} template<class T>void chmax(T&a,const T&b){if(a<b)a=b;} ll nextLong() { ll x; scanf("%lld", &x); return x;} const int INF = 1001001001; const int MAX_N = 112345; int fromS[MAX_N][2]; int fromG[MAX_N][2]; int N; vector<int> g[MAX_N]; void search(int s, int dist[MAX_N][2]) { REP(i, MAX_N) REP(j, 2) dist[i][j] = INF; queue<pair<int,int>> q; q.push({s, 0}); dist[s][0] = 0; while (!q.empty()) { auto p = q.front(); q.pop(); int u = p.first; int f = p.second; for (int v : g[u]) { if (dist[v][1-f] > dist[u][f] + 1) { dist[v][1-f] = dist[u][f] + 1; q.push({v, 1-f}); } } } } int main2() { REP(i, MAX_N) g[i].clear(); N = nextLong(); int M = nextLong(); int P = nextLong(); int S = nextLong() - 1; int G = nextLong() - 1; REP(i, M) { int a = nextLong() - 1; int b = nextLong() - 1; g[a].push_back(b); g[b].push_back(a); } search(S, fromS); search(G, fromG); // REP(i, N) { cout << fromS[i][0] << " "; } cout << endl; // REP(i, N) { cout << fromS[i][1] << " "; } cout << endl; // REP(i, N) { cout << fromG[i][0] << " "; } cout << endl; // REP(i, N) { cout << fromG[i][1] << " "; } cout << endl; if (fromS[G][P%2] == INF) { cout << -1 << endl; return 0; } vector<int> ans; REP(i, N) { bool ok = false; REP(f1, 2) REP(f2, 2) { int pp = fromS[i][f1] + fromG[i][f2]; if (pp <= P && (P - pp) % 2 == 0) ok = true; } if (ok) ans.push_back(i+1); } cout << ans.size() << endl; REP(i, ans.size()) cout << ans[i] << '\n'; return 0; } int main() { #ifdef LOCAL for (;!cin.eof();cin>>ws) #endif main2(); return 0; }