oj.uz

Submission #655694

# Submission time Handle Problem Language Result Execution time Memory
655694 2022-11-05T10:25:14 Z 600Mihnea From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 135804 KB 
// pana la ora 1 
bool home = 0;
bool verbose = 1;

#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
#include <queue>


using namespace std;

struct T {
  int v;
  int r;
};

const int N = 250000 + 7;
const int V = (int)1e6 + 7;
const int INF = (int)1e9 + 7;
int n;
int m;
int cnt_cycles;
int suml;
vector<pair<int, int>> edges;
vector<int> cycles[N];
int cycle_id[N];
int cycle_location[N];
int single_vertex_id[N];
vector<int> cycle_vertex_id[N];
int dp[V];
T what[V];
int y;
vector<int> g[N];

priority_queue<pair<int, int>> pq;

void relax(int id, int d) {
  assert(1 <= id && id <= y);
  if (d < dp[id]) {
    dp[id] = d;
    pq.push({ -dp[id], id });
  }
}

int main() {
  if (!home) {
    verbose = 0;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  }
  if (home) {
    verbose = 1;
   // FILE* stream;
    //freopen_s(&stream, "input.txt", "r", stdin);
  }

  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
    edges.push_back({ a, b });
  }

  cin >> cnt_cycles;
  for (int i = 1; i <= cnt_cycles; i++) {
    int l;
    cin >> l;
    suml += l;
    cycles[i].resize(l);
    for (int j = 0; j < (int)cycles[i].size(); j++) {
      cin >> cycles[i][j];
      assert(cycle_id[cycles[i][j]] == 0);
      cycle_id[cycles[i][j]] = i;
      cycle_location[cycles[i][j]] = j;
    }
    if (verbose) {
      cout << " ---> ";
      for (auto& v : cycles[i]) {
        cout << v << " ";
      }
      cout << "\n";
    }
  }
  for (int a = 1; a <= n; a++) {
    if (cycle_id[a] == 0) {
      y++;
      single_vertex_id[a] = y;
      what[y] = { a, 0 };
    }
    else {
      int id = cycle_id[a];
      cycle_vertex_id[a].resize((int) cycles[id].size());
      for (int j = 0; j < (int)cycles[id].size(); j++) {
        y++;
        cycle_vertex_id[a][j] = y;
        what[y] = { a, j };
      }
    }
  }
  for (int i = 1; i <= y; i++) {
    dp[i] = INF;
  }
  if (verbose) {
    cout << "################################################################################### \n";
  }
  assert(cycle_id[1] == 0);
  assert(cycle_id[n] == 0);

  dp[single_vertex_id[1]] = 0;
  pq.push({ 0, single_vertex_id[1] });

  while (!pq.empty()) {
    int d = -pq.top().first;
    int idv = pq.top().second;
    pq.pop();
    if (dp[idv] != d) {
      continue;
    }
    int vertex = what[idv].v;
    int r = what[idv].r;
    if (cycle_id[vertex] == 0) {
      assert(r == 0);
      for (auto& vecin : g[vertex]) {
        if (cycle_id[vecin] == 0) {
          // vecin is a single vertex
          relax(single_vertex_id[vecin], d + 1);
        }
        else {
          // vecin is on a cycle
          int cycle_vecin = cycle_id[vecin];
          int l_vecin = cycles[cycle_vecin].size();
          for (int twait = 0; twait < l_vecin; twait++) {
            // la momentul d + 1 + twait
            if ((d + 1 + twait) % l_vecin == cycle_location[vecin]) {
              continue;
            }
            relax(cycle_vertex_id[vecin][(d + 1 + twait) % l_vecin], d + 1 + twait);
          }
        }
      }
    }
    else {
      int cycle = cycle_id[vertex];
      int l = cycles[cycle].size();

      /*
        wait a moment here
      */

      if ((d + 1) % l != cycle_location[vertex]) {
        relax(cycle_vertex_id[vertex][(d + 1) % l], d + 1);
      }

      /*
        don't wait a moment here
      */

      assert(0 <= r && r < l);
      assert(d % l == r);
      for (auto& vecin : g[vertex]) {
        if (cycle_id[vecin] == 0) {
          // vecin is a single vertex
          relax(single_vertex_id[vecin], d + 1);
        }
        else {
          // vecin is on a cycle
          int cycle_vecin = cycle_id[vecin];
          int l_vecin = cycles[cycle_vecin].size();
          if (cycle_vecin == cycle) {
            // vecin is on the same cycle
            if ((d + 1) % l_vecin == cycle_location[vecin]) {
              continue;
            }
            if (d % l_vecin == cycle_location[vecin] && (d + 1) % l_vecin == cycle_location[vertex]) {
              continue;
            }

            relax(cycle_vertex_id[vecin][(d + 1) % l_vecin], d + 1);
            /*
            
            vertex -> vecin <- vecin2


            */
          }
          else {
            // vecin is on a different cycle
            if ((d + 1) % l_vecin == cycle_location[vecin]) {
              continue;
            }
            relax(cycle_vertex_id[vecin][(d + 1) % l_vecin], d + 1);
          }
        }
      }
    }
  }

  int sol = dp[single_vertex_id[n]];
  if (sol == INF) {
    cout << "impossible\n";
    return 0;
  }
  cout << sol << "\n";
  return 0;
  /*for (auto& edge : edges) {
    int a = edge.first, b = edge.second;
    if (cycle_id[a] == 0 && cycle_id[b] == 0) {
      // just a normal edge
      addEdge(single_vertex_id[a], single_vertex_id[b], 1);
      continue;
    }
    if (cycle_id[a] != 0 && cycle_id[b] == 0) {
      swap(a, b);
    }
    if (cycle_id[a] == 0 && cycle_id[b] != 0) {

      continue;
    }
    assert(cycle_id[a] != 0 && cycle_id[b] != 0);
  }*/
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 20552 KB Output is correct
2 Correct 61 ms 25372 KB Output is correct
3 Correct 63 ms 25080 KB Output is correct
4 Correct 108 ms 25452 KB Output is correct
5 Correct 11 ms 18132 KB Output is correct
6 Correct 66 ms 25036 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 20428 KB Output is correct
2 Correct 58 ms 25344 KB Output is correct
3 Correct 84 ms 25108 KB Output is correct
4 Correct 90 ms 25460 KB Output is correct
5 Correct 11 ms 18132 KB Output is correct
6 Correct 63 ms 25088 KB Output is correct
7 Correct 54 ms 24896 KB Output is correct
8 Correct 54 ms 24844 KB Output is correct
9 Correct 69 ms 24732 KB Output is correct
10 Correct 79 ms 25024 KB Output is correct
11 Correct 60 ms 24864 KB Output is correct
12 Correct 63 ms 24860 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 20428 KB Output is correct
2 Correct 58 ms 25344 KB Output is correct
3 Correct 84 ms 25108 KB Output is correct
4 Correct 90 ms 25460 KB Output is correct
5 Correct 11 ms 18132 KB Output is correct
6 Correct 63 ms 25088 KB Output is correct
7 Correct 54 ms 24896 KB Output is correct
8 Correct 54 ms 24844 KB Output is correct
9 Correct 69 ms 24732 KB Output is correct
10 Correct 79 ms 25024 KB Output is correct
11 Correct 60 ms 24864 KB Output is correct
12 Correct 63 ms 24860 KB Output is correct
13 Correct 90 ms 20432 KB Output is correct
14 Correct 59 ms 25388 KB Output is correct
15 Correct 69 ms 25164 KB Output is correct
16 Correct 91 ms 25412 KB Output is correct
17 Correct 11 ms 18132 KB Output is correct
18 Correct 67 ms 25152 KB Output is correct
19 Correct 59 ms 24816 KB Output is correct
20 Correct 62 ms 24792 KB Output is correct
21 Correct 80 ms 24788 KB Output is correct
22 Correct 80 ms 25068 KB Output is correct
23 Correct 59 ms 24880 KB Output is correct
24 Correct 67 ms 24848 KB Output is correct
25 Correct 1441 ms 129688 KB Output is correct
26 Correct 1353 ms 135804 KB Output is correct
27 Correct 1240 ms 129344 KB Output is correct
28 Correct 1004 ms 133340 KB Output is correct
29 Execution timed out 6056 ms 124924 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 20428 KB Output is correct
2 Correct 58 ms 25344 KB Output is correct
3 Correct 84 ms 25108 KB Output is correct
4 Correct 90 ms 25460 KB Output is correct
5 Correct 11 ms 18132 KB Output is correct
6 Correct 63 ms 25088 KB Output is correct
7 Correct 54 ms 24896 KB Output is correct
8 Correct 54 ms 24844 KB Output is correct
9 Correct 69 ms 24732 KB Output is correct
10 Correct 79 ms 25024 KB Output is correct
11 Correct 60 ms 24864 KB Output is correct
12 Correct 63 ms 24860 KB Output is correct
13 Correct 90 ms 20432 KB Output is correct
14 Correct 59 ms 25388 KB Output is correct
15 Correct 69 ms 25164 KB Output is correct
16 Correct 91 ms 25412 KB Output is correct
17 Correct 11 ms 18132 KB Output is correct
18 Correct 67 ms 25152 KB Output is correct
19 Correct 59 ms 24816 KB Output is correct
20 Correct 62 ms 24792 KB Output is correct
21 Correct 80 ms 24788 KB Output is correct
22 Correct 80 ms 25068 KB Output is correct
23 Correct 59 ms 24880 KB Output is correct
24 Correct 67 ms 24848 KB Output is correct
25 Correct 1441 ms 129688 KB Output is correct
26 Correct 1353 ms 135804 KB Output is correct
27 Correct 1240 ms 129344 KB Output is correct
28 Correct 1004 ms 133340 KB Output is correct
29 Execution timed out 6056 ms 124924 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 20552 KB Output is correct
2 Correct 61 ms 25372 KB Output is correct
3 Correct 63 ms 25080 KB Output is correct
4 Correct 108 ms 25452 KB Output is correct
5 Correct 11 ms 18132 KB Output is correct
6 Correct 66 ms 25036 KB Output is correct
7 Correct 85 ms 20428 KB Output is correct
8 Correct 58 ms 25344 KB Output is correct
9 Correct 84 ms 25108 KB Output is correct
10 Correct 90 ms 25460 KB Output is correct
11 Correct 11 ms 18132 KB Output is correct
12 Correct 63 ms 25088 KB Output is correct
13 Correct 54 ms 24896 KB Output is correct
14 Correct 54 ms 24844 KB Output is correct
15 Correct 69 ms 24732 KB Output is correct
16 Correct 79 ms 25024 KB Output is correct
17 Correct 60 ms 24864 KB Output is correct
18 Correct 63 ms 24860 KB Output is correct
19 Correct 10 ms 17876 KB Output is correct
20 Correct 10 ms 17956 KB Output is correct
21 Correct 10 ms 17876 KB Output is correct
22 Correct 90 ms 20548 KB Output is correct
23 Correct 72 ms 25384 KB Output is correct
24 Correct 62 ms 25148 KB Output is correct
25 Correct 94 ms 25408 KB Output is correct
26 Correct 13 ms 18216 KB Output is correct
27 Correct 66 ms 25148 KB Output is correct
28 Correct 55 ms 24804 KB Output is correct
29 Correct 58 ms 24800 KB Output is correct
30 Correct 62 ms 24756 KB Output is correct
31 Correct 73 ms 25036 KB Output is correct
32 Correct 90 ms 24896 KB Output is correct
33 Correct 60 ms 24820 KB Output is correct
34 Correct 1459 ms 129768 KB Output is correct
35 Correct 1472 ms 126260 KB Output is correct
36 Correct 1604 ms 126176 KB Output is correct
37 Incorrect 1377 ms 132504 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 20552 KB Output is correct
2 Correct 61 ms 25372 KB Output is correct
3 Correct 63 ms 25080 KB Output is correct
4 Correct 108 ms 25452 KB Output is correct
5 Correct 11 ms 18132 KB Output is correct
6 Correct 66 ms 25036 KB Output is correct
7 Correct 85 ms 20428 KB Output is correct
8 Correct 58 ms 25344 KB Output is correct
9 Correct 84 ms 25108 KB Output is correct
10 Correct 90 ms 25460 KB Output is correct
11 Correct 11 ms 18132 KB Output is correct
12 Correct 63 ms 25088 KB Output is correct
13 Correct 54 ms 24896 KB Output is correct
14 Correct 54 ms 24844 KB Output is correct
15 Correct 69 ms 24732 KB Output is correct
16 Correct 79 ms 25024 KB Output is correct
17 Correct 60 ms 24864 KB Output is correct
18 Correct 63 ms 24860 KB Output is correct
19 Correct 90 ms 20432 KB Output is correct
20 Correct 59 ms 25388 KB Output is correct
21 Correct 69 ms 25164 KB Output is correct
22 Correct 91 ms 25412 KB Output is correct
23 Correct 11 ms 18132 KB Output is correct
24 Correct 67 ms 25152 KB Output is correct
25 Correct 59 ms 24816 KB Output is correct
26 Correct 62 ms 24792 KB Output is correct
27 Correct 80 ms 24788 KB Output is correct
28 Correct 80 ms 25068 KB Output is correct
29 Correct 59 ms 24880 KB Output is correct
30 Correct 67 ms 24848 KB Output is correct
31 Correct 1441 ms 129688 KB Output is correct
32 Correct 1353 ms 135804 KB Output is correct
33 Correct 1240 ms 129344 KB Output is correct
34 Correct 1004 ms 133340 KB Output is correct
35 Execution timed out 6056 ms 124924 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 20552 KB Output is correct
2 Correct 61 ms 25372 KB Output is correct
3 Correct 63 ms 25080 KB Output is correct
4 Correct 108 ms 25452 KB Output is correct
5 Correct 11 ms 18132 KB Output is correct
6 Correct 66 ms 25036 KB Output is correct
7 Correct 85 ms 20428 KB Output is correct
8 Correct 58 ms 25344 KB Output is correct
9 Correct 84 ms 25108 KB Output is correct
10 Correct 90 ms 25460 KB Output is correct
11 Correct 11 ms 18132 KB Output is correct
12 Correct 63 ms 25088 KB Output is correct
13 Correct 54 ms 24896 KB Output is correct
14 Correct 54 ms 24844 KB Output is correct
15 Correct 69 ms 24732 KB Output is correct
16 Correct 79 ms 25024 KB Output is correct
17 Correct 60 ms 24864 KB Output is correct
18 Correct 63 ms 24860 KB Output is correct
19 Correct 90 ms 20432 KB Output is correct
20 Correct 59 ms 25388 KB Output is correct
21 Correct 69 ms 25164 KB Output is correct
22 Correct 91 ms 25412 KB Output is correct
23 Correct 11 ms 18132 KB Output is correct
24 Correct 67 ms 25152 KB Output is correct
25 Correct 59 ms 24816 KB Output is correct
26 Correct 62 ms 24792 KB Output is correct
27 Correct 80 ms 24788 KB Output is correct
28 Correct 80 ms 25068 KB Output is correct
29 Correct 59 ms 24880 KB Output is correct
30 Correct 67 ms 24848 KB Output is correct
31 Correct 1441 ms 129688 KB Output is correct
32 Correct 1353 ms 135804 KB Output is correct
33 Correct 1240 ms 129344 KB Output is correct
34 Correct 1004 ms 133340 KB Output is correct
35 Execution timed out 6056 ms 124924 KB Time limit exceeded
36 Halted 0 ms 0 KB -