Submission #463795

#TimeUsernameProblemLanguageResultExecution timeMemory
463795AlexLuchianov007 (CEOI14_007)C++14
100 / 100
316 ms17696 KiB
#include <iostream> #include <fstream> #include <vector> #include <queue> #include <algorithm> using ll = long long; int const nmax = 200000; std::vector<int> bfs(int n, int node, std::vector<std::vector<int>> &g) { std::vector<int> dist(n, -1); std::queue<int> q; q.push(node); dist[node] = 0; while(0 < q.size()) { node = q.front(); q.pop(); for(int h = 0; h < g[node].size(); h++) { int to = g[node][h]; if(dist[to] == -1) { dist[to] = dist[node] + 1; q.push(to); } } } return dist; } int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); int n, m; std::cin >> n >> m; int start1, start2, stop1, stop2; std::cin >> start1 >> start2 >> stop1 >> stop2; start1--; start2--; stop1--; stop2--; std::vector<std::vector<int>> g(n); for(int i = 1;i <= m; i++) { int x, y; std::cin >> x >> y; x--; y--; g[x].push_back(y); g[y].push_back(x); } std::vector<int> dist1(n), dist2(n); std::vector<int> trap1(n), trap2(n); dist1 = bfs(n, start1, g); dist2 = bfs(n, start2, g); trap1 = bfs(n, stop1, g); trap2 = bfs(n, stop2, g); int a = dist2[stop1] - dist1[stop1]; int b = dist2[stop2] - dist1[stop2]; if(a < 0 || b < 0) std::cout << -1 << '\n'; else { int juke = 0, juke2 = 0; for(int i = 0; i < n; i++) if(dist1[i] + trap1[i] == dist1[stop1] && dist1[i] + trap2[i] == dist1[stop2]) juke = std::max(juke, dist1[i]); for(int i = 0; i < n; i++) if(dist2[i] + trap1[i] == dist2[stop1] && dist2[i] + trap2[i] == dist2[stop2]) juke2 = std::max(juke2, dist2[i]); if(a != b) std::cout << std::min(a, b) << '\n'; else { if(juke + a < juke2) std::cout << a - 1 << '\n'; else std::cout << a << '\n'; } } return 0; }

Compilation message (stderr)

007.cpp: In function 'std::vector<int> bfs(int, int, std::vector<std::vector<int> >&)':
007.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int h = 0; h < g[node].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...