Submission #95411

#TimeUsernameProblemLanguageResultExecution timeMemory
95411popovicirobert007 (CEOI14_007)C++14
100 / 100
282 ms16248 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long #define ld long double // 217 // 44 using namespace std; const int MAXN = (int) 2e5; vector <int> g[MAXN + 1]; int dst[MAXN + 1][2]; inline void bfs(int nod, bool t) { queue <int> Q; dst[nod][t] = 1; Q.push(nod); while(Q.size()) { nod = Q.front(); Q.pop(); for(auto it : g[nod]) { if(dst[it][t] == 0) { dst[it][t] = dst[nod][t] + 1; Q.push(it); } } } } int dfs(int nod) { for(auto it : g[nod]) { if(dst[nod][0] == dst[it][0] + 1 && dst[nod][1] == dst[it][1] + 1) { return dfs(it) + 1; } } return 0; } int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, n, m, s, d, a, b; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> m; cin >> s >> d >> a >> b; for(i = 1; i <= m; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } bfs(a, 0); bfs(b, 1); if(dst[s][0] - dst[d][0] != dst[s][1] - dst[d][1]) { cout << max(-1, min(dst[d][0] - dst[s][0], dst[d][1] - dst[s][1])); return 0; } int cnt_s = dfs(s), cnt_d = dfs(d); int ans = -1; if(dst[s][0] <= dst[d][0]) { if(cnt_s + dst[d][0] - dst[s][0] >= cnt_d) { ans = max(ans, dst[d][0] - dst[s][0]); } else { ans = max(ans, dst[d][0] - dst[s][0] - 1); } } cout << ans; //cin.close(); //cout.close(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...