oj.uz

Submission #463794

# Submission time Handle Problem Language Result Execution time Memory
463794 2021-08-11T18:45:53 Z AlexLuchianov 007 (CEOI14_007) C++14
0 / 100
 305 ms 17700 KB 
#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(juke, 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

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++) {
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Incorrect 1 ms 204 KB Output isn't correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Incorrect 1 ms 360 KB Output isn't correct
18 Incorrect 1 ms 332 KB Output isn't correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Incorrect 1 ms 332 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3340 KB Output is correct
2 Incorrect 35 ms 4732 KB Output isn't correct
3 Correct 25 ms 3524 KB Output is correct
4 Incorrect 36 ms 4896 KB Output isn't correct
5 Correct 25 ms 3208 KB Output is correct
6 Correct 27 ms 3656 KB Output is correct
7 Correct 27 ms 3916 KB Output is correct
8 Correct 28 ms 3980 KB Output is correct
9 Incorrect 41 ms 4408 KB Output isn't correct
10 Correct 177 ms 9124 KB Output is correct
11 Incorrect 62 ms 7056 KB Output isn't correct
12 Correct 94 ms 8780 KB Output is correct
13 Incorrect 73 ms 7600 KB Output isn't correct
14 Correct 59 ms 6436 KB Output is correct
15 Correct 75 ms 8940 KB Output is correct
16 Correct 82 ms 9396 KB Output is correct
17 Correct 84 ms 8408 KB Output is correct
18 Incorrect 84 ms 8400 KB Output isn't correct
19 Correct 109 ms 9668 KB Output is correct
20 Incorrect 225 ms 12640 KB Output isn't correct
21 Incorrect 112 ms 12228 KB Output isn't correct
22 Correct 101 ms 10660 KB Output is correct
23 Correct 117 ms 12084 KB Output is correct
24 Correct 103 ms 11968 KB Output is correct
25 Incorrect 100 ms 11328 KB Output isn't correct
26 Correct 102 ms 10764 KB Output is correct
27 Correct 114 ms 12220 KB Output is correct
28 Correct 130 ms 12356 KB Output is correct
29 Correct 151 ms 12096 KB Output is correct
30 Incorrect 215 ms 13756 KB Output isn't correct
31 Incorrect 128 ms 14024 KB Output isn't correct
32 Correct 125 ms 12092 KB Output is correct
33 Correct 115 ms 12448 KB Output is correct
34 Incorrect 131 ms 13076 KB Output isn't correct
35 Incorrect 160 ms 12620 KB Output isn't correct
36 Incorrect 122 ms 13220 KB Output isn't correct
37 Correct 151 ms 14788 KB Output is correct
38 Correct 144 ms 14424 KB Output is correct
39 Correct 184 ms 14452 KB Output is correct
40 Incorrect 216 ms 15812 KB Output isn't correct
41 Correct 305 ms 17700 KB Output is correct