oj.uz

Submission #463793

# Submission time Handle Problem Language Result Execution time Memory
463793 2021-08-11T18:42:59 Z AlexLuchianov 007 (CEOI14_007) C++14
0 / 100
 376 ms 24972 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(juke + std::min(a, b) < juke2)
      std::cout << std::min(a, b) - 1 << '\n';
    else
      std::cout << std::min(a, b) << '\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 0 ms 204 KB Output is correct
3 Correct 1 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 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 1 ms 204 KB Output isn't correct
9 Correct 1 ms 332 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 332 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 23 ms 3820 KB Output is correct
2 Incorrect 32 ms 5388 KB Output isn't correct
3 Correct 26 ms 4044 KB Output is correct
4 Incorrect 33 ms 5608 KB Output isn't correct
5 Correct 24 ms 3684 KB Output is correct
6 Correct 24 ms 4172 KB Output is correct
7 Correct 28 ms 4492 KB Output is correct
8 Correct 28 ms 4484 KB Output is correct
9 Incorrect 40 ms 5376 KB Output isn't correct
10 Correct 155 ms 14332 KB Output is correct
11 Incorrect 59 ms 8180 KB Output isn't correct
12 Correct 79 ms 10188 KB Output is correct
13 Incorrect 73 ms 8740 KB Output isn't correct
14 Correct 54 ms 7396 KB Output is correct
15 Correct 81 ms 10300 KB Output is correct
16 Correct 87 ms 10852 KB Output is correct
17 Correct 69 ms 9668 KB Output is correct
18 Incorrect 78 ms 9708 KB Output isn't correct
19 Correct 122 ms 12196 KB Output is correct
20 Incorrect 201 ms 18124 KB Output isn't correct
21 Incorrect 126 ms 14276 KB Output isn't correct
22 Correct 115 ms 12360 KB Output is correct
23 Correct 122 ms 13996 KB Output is correct
24 Correct 114 ms 13912 KB Output is correct
25 Incorrect 109 ms 13184 KB Output isn't correct
26 Correct 114 ms 12492 KB Output is correct
27 Correct 127 ms 14184 KB Output is correct
28 Correct 139 ms 14172 KB Output is correct
29 Correct 150 ms 15420 KB Output is correct
30 Incorrect 231 ms 19792 KB Output isn't correct
31 Incorrect 154 ms 16360 KB Output isn't correct
32 Correct 131 ms 14060 KB Output is correct
33 Correct 118 ms 14584 KB Output is correct
34 Incorrect 165 ms 15432 KB Output isn't correct
35 Incorrect 125 ms 14788 KB Output isn't correct
36 Incorrect 114 ms 15220 KB Output isn't correct
37 Correct 149 ms 17260 KB Output is correct
38 Correct 161 ms 16900 KB Output is correct
39 Correct 181 ms 16904 KB Output is correct
40 Incorrect 220 ms 20204 KB Output isn't correct
41 Correct 376 ms 24972 KB Output is correct