oj.uz

Submission #655716

# Submission time Handle Problem Language Result Execution time Memory
655716 2022-11-05T11:10:05 Z 600Mihnea From Hacks to Snitches (BOI21_watchmen) C++17
50 / 100
 6000 ms 227756 KB 
// pana la ora 1
bool home = 0;
bool verbose = 1;

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


using namespace std;

struct T {
  int v;
  int r;
};

const int N = 250000 + 7;
const int V = (int)1e7 + 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];
vector<int> splash_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) {
  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];
      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());
      splash_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 j = 0; j < (int)cycles[id].size(); j++) {
        y++;
        splash_vertex_id[a][j] = y;
        what[y] = { a, -(j + 1) };
      }
    }
  }
  for (int i = 1; i <= y; i++) {
    dp[i] = INF;
  }
  if (verbose) {
    cout << "################################################################################### \n";
  }

  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 (r < 0) {
      r *= -1;
      r--;

      int cycle = cycle_id[vertex];
      int l = cycles[cycle].size();
      relax(splash_vertex_id[vertex][(d + 1) % l], d + 1);
      if (d % l != cycle_location[vertex]) {
        relax(cycle_vertex_id[vertex][d % l], d);
      }
      continue;
    }
    if (cycle_id[vertex] == 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();
          relax(splash_vertex_id[vecin][(d + 1) % l_vecin], d + 1);
          continue;
          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);
          }
        }
      }
        continue;
    }
    if (cycle_id[vertex] != 0) {
      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
      */

      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
            for (int j = 0; j <= l_vecin; j++) {
              int twait = j * l;
              // 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);
            }
          }
        }
      }
      continue;
    }
  }

  int sol = dp[single_vertex_id[n]];
  if (sol == INF) {
    cout << "impossible\n";
    return 0;
  }
  cout << sol << "\n";
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26316 KB Output is correct
2 Correct 77 ms 31468 KB Output is correct
3 Correct 66 ms 31072 KB Output is correct
4 Correct 93 ms 31224 KB Output is correct
5 Correct 14 ms 24232 KB Output is correct
6 Correct 67 ms 31092 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26336 KB Output is correct
2 Correct 65 ms 31424 KB Output is correct
3 Correct 63 ms 31088 KB Output is correct
4 Correct 95 ms 31148 KB Output is correct
5 Correct 16 ms 24276 KB Output is correct
6 Correct 66 ms 31084 KB Output is correct
7 Correct 58 ms 30840 KB Output is correct
8 Correct 96 ms 30752 KB Output is correct
9 Correct 63 ms 30680 KB Output is correct
10 Correct 71 ms 31164 KB Output is correct
11 Correct 62 ms 30784 KB Output is correct
12 Correct 62 ms 30812 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26336 KB Output is correct
2 Correct 65 ms 31424 KB Output is correct
3 Correct 63 ms 31088 KB Output is correct
4 Correct 95 ms 31148 KB Output is correct
5 Correct 16 ms 24276 KB Output is correct
6 Correct 66 ms 31084 KB Output is correct
7 Correct 58 ms 30840 KB Output is correct
8 Correct 96 ms 30752 KB Output is correct
9 Correct 63 ms 30680 KB Output is correct
10 Correct 71 ms 31164 KB Output is correct
11 Correct 62 ms 30784 KB Output is correct
12 Correct 62 ms 30812 KB Output is correct
13 Correct 58 ms 26392 KB Output is correct
14 Correct 69 ms 31416 KB Output is correct
15 Correct 76 ms 31104 KB Output is correct
16 Correct 94 ms 31180 KB Output is correct
17 Correct 15 ms 24320 KB Output is correct
18 Correct 69 ms 31012 KB Output is correct
19 Correct 58 ms 30784 KB Output is correct
20 Correct 58 ms 30748 KB Output is correct
21 Correct 57 ms 30712 KB Output is correct
22 Correct 69 ms 30924 KB Output is correct
23 Correct 66 ms 30688 KB Output is correct
24 Correct 64 ms 30824 KB Output is correct
25 Correct 1349 ms 99932 KB Output is correct
26 Correct 1317 ms 106328 KB Output is correct
27 Correct 1246 ms 99348 KB Output is correct
28 Correct 958 ms 103260 KB Output is correct
29 Correct 3291 ms 93588 KB Output is correct
30 Correct 3212 ms 102144 KB Output is correct
31 Correct 1460 ms 111600 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26336 KB Output is correct
2 Correct 65 ms 31424 KB Output is correct
3 Correct 63 ms 31088 KB Output is correct
4 Correct 95 ms 31148 KB Output is correct
5 Correct 16 ms 24276 KB Output is correct
6 Correct 66 ms 31084 KB Output is correct
7 Correct 58 ms 30840 KB Output is correct
8 Correct 96 ms 30752 KB Output is correct
9 Correct 63 ms 30680 KB Output is correct
10 Correct 71 ms 31164 KB Output is correct
11 Correct 62 ms 30784 KB Output is correct
12 Correct 62 ms 30812 KB Output is correct
13 Correct 58 ms 26392 KB Output is correct
14 Correct 69 ms 31416 KB Output is correct
15 Correct 76 ms 31104 KB Output is correct
16 Correct 94 ms 31180 KB Output is correct
17 Correct 15 ms 24320 KB Output is correct
18 Correct 69 ms 31012 KB Output is correct
19 Correct 58 ms 30784 KB Output is correct
20 Correct 58 ms 30748 KB Output is correct
21 Correct 57 ms 30712 KB Output is correct
22 Correct 69 ms 30924 KB Output is correct
23 Correct 66 ms 30688 KB Output is correct
24 Correct 64 ms 30824 KB Output is correct
25 Correct 1349 ms 99932 KB Output is correct
26 Correct 1317 ms 106328 KB Output is correct
27 Correct 1246 ms 99348 KB Output is correct
28 Correct 958 ms 103260 KB Output is correct
29 Correct 3291 ms 93588 KB Output is correct
30 Correct 3212 ms 102144 KB Output is correct
31 Correct 1460 ms 111600 KB Output is correct
32 Correct 58 ms 26308 KB Output is correct
33 Correct 75 ms 31392 KB Output is correct
34 Correct 71 ms 31060 KB Output is correct
35 Correct 93 ms 31168 KB Output is correct
36 Correct 15 ms 24336 KB Output is correct
37 Correct 75 ms 31016 KB Output is correct
38 Correct 59 ms 30804 KB Output is correct
39 Correct 60 ms 30788 KB Output is correct
40 Correct 61 ms 30692 KB Output is correct
41 Correct 69 ms 30920 KB Output is correct
42 Correct 65 ms 30784 KB Output is correct
43 Correct 63 ms 30888 KB Output is correct
44 Correct 1447 ms 104072 KB Output is correct
45 Correct 1410 ms 110664 KB Output is correct
46 Correct 1303 ms 103496 KB Output is correct
47 Correct 1089 ms 107564 KB Output is correct
48 Correct 3235 ms 97900 KB Output is correct
49 Correct 3475 ms 101864 KB Output is correct
50 Correct 1394 ms 111744 KB Output is correct
51 Correct 2077 ms 174292 KB Output is correct
52 Correct 2634 ms 227756 KB Output is correct
53 Correct 2730 ms 181780 KB Output is correct
54 Correct 991 ms 103660 KB Output is correct
55 Execution timed out 6100 ms 173572 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26316 KB Output is correct
2 Correct 77 ms 31468 KB Output is correct
3 Correct 66 ms 31072 KB Output is correct
4 Correct 93 ms 31224 KB Output is correct
5 Correct 14 ms 24232 KB Output is correct
6 Correct 67 ms 31092 KB Output is correct
7 Correct 58 ms 26336 KB Output is correct
8 Correct 65 ms 31424 KB Output is correct
9 Correct 63 ms 31088 KB Output is correct
10 Correct 95 ms 31148 KB Output is correct
11 Correct 16 ms 24276 KB Output is correct
12 Correct 66 ms 31084 KB Output is correct
13 Correct 58 ms 30840 KB Output is correct
14 Correct 96 ms 30752 KB Output is correct
15 Correct 63 ms 30680 KB Output is correct
16 Correct 71 ms 31164 KB Output is correct
17 Correct 62 ms 30784 KB Output is correct
18 Correct 62 ms 30812 KB Output is correct
19 Correct 13 ms 23820 KB Output is correct
20 Correct 15 ms 23764 KB Output is correct
21 Correct 13 ms 23832 KB Output is correct
22 Correct 59 ms 26308 KB Output is correct
23 Correct 73 ms 31516 KB Output is correct
24 Correct 66 ms 31060 KB Output is correct
25 Correct 94 ms 31232 KB Output is correct
26 Correct 15 ms 24276 KB Output is correct
27 Correct 72 ms 31016 KB Output is correct
28 Correct 58 ms 30804 KB Output is correct
29 Correct 60 ms 30728 KB Output is correct
30 Correct 62 ms 30796 KB Output is correct
31 Correct 84 ms 31036 KB Output is correct
32 Correct 72 ms 30720 KB Output is correct
33 Correct 62 ms 30816 KB Output is correct
34 Correct 1318 ms 99668 KB Output is correct
35 Correct 1397 ms 96008 KB Output is correct
36 Correct 1407 ms 96128 KB Output is correct
37 Correct 1231 ms 102520 KB Output is correct
38 Correct 1377 ms 96640 KB Output is correct
39 Correct 2238 ms 91472 KB Output is correct
40 Correct 1853 ms 92892 KB Output is correct
41 Correct 1465 ms 91564 KB Output is correct
42 Correct 1324 ms 96708 KB Output is correct
43 Correct 1369 ms 102628 KB Output is correct
44 Correct 1363 ms 102800 KB Output is correct
45 Correct 1410 ms 96520 KB Output is correct
46 Correct 1363 ms 96664 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26316 KB Output is correct
2 Correct 77 ms 31468 KB Output is correct
3 Correct 66 ms 31072 KB Output is correct
4 Correct 93 ms 31224 KB Output is correct
5 Correct 14 ms 24232 KB Output is correct
6 Correct 67 ms 31092 KB Output is correct
7 Correct 58 ms 26336 KB Output is correct
8 Correct 65 ms 31424 KB Output is correct
9 Correct 63 ms 31088 KB Output is correct
10 Correct 95 ms 31148 KB Output is correct
11 Correct 16 ms 24276 KB Output is correct
12 Correct 66 ms 31084 KB Output is correct
13 Correct 58 ms 30840 KB Output is correct
14 Correct 96 ms 30752 KB Output is correct
15 Correct 63 ms 30680 KB Output is correct
16 Correct 71 ms 31164 KB Output is correct
17 Correct 62 ms 30784 KB Output is correct
18 Correct 62 ms 30812 KB Output is correct
19 Correct 58 ms 26392 KB Output is correct
20 Correct 69 ms 31416 KB Output is correct
21 Correct 76 ms 31104 KB Output is correct
22 Correct 94 ms 31180 KB Output is correct
23 Correct 15 ms 24320 KB Output is correct
24 Correct 69 ms 31012 KB Output is correct
25 Correct 58 ms 30784 KB Output is correct
26 Correct 58 ms 30748 KB Output is correct
27 Correct 57 ms 30712 KB Output is correct
28 Correct 69 ms 30924 KB Output is correct
29 Correct 66 ms 30688 KB Output is correct
30 Correct 64 ms 30824 KB Output is correct
31 Correct 1349 ms 99932 KB Output is correct
32 Correct 1317 ms 106328 KB Output is correct
33 Correct 1246 ms 99348 KB Output is correct
34 Correct 958 ms 103260 KB Output is correct
35 Correct 3291 ms 93588 KB Output is correct
36 Correct 3212 ms 102144 KB Output is correct
37 Correct 1460 ms 111600 KB Output is correct
38 Correct 13 ms 23820 KB Output is correct
39 Correct 15 ms 23764 KB Output is correct
40 Correct 13 ms 23832 KB Output is correct
41 Correct 59 ms 26308 KB Output is correct
42 Correct 73 ms 31516 KB Output is correct
43 Correct 66 ms 31060 KB Output is correct
44 Correct 94 ms 31232 KB Output is correct
45 Correct 15 ms 24276 KB Output is correct
46 Correct 72 ms 31016 KB Output is correct
47 Correct 58 ms 30804 KB Output is correct
48 Correct 60 ms 30728 KB Output is correct
49 Correct 62 ms 30796 KB Output is correct
50 Correct 84 ms 31036 KB Output is correct
51 Correct 72 ms 30720 KB Output is correct
52 Correct 62 ms 30816 KB Output is correct
53 Correct 1318 ms 99668 KB Output is correct
54 Correct 1397 ms 96008 KB Output is correct
55 Correct 1407 ms 96128 KB Output is correct
56 Correct 1231 ms 102520 KB Output is correct
57 Correct 1377 ms 96640 KB Output is correct
58 Correct 2238 ms 91472 KB Output is correct
59 Correct 1853 ms 92892 KB Output is correct
60 Correct 1465 ms 91564 KB Output is correct
61 Correct 1324 ms 96708 KB Output is correct
62 Correct 1369 ms 102628 KB Output is correct
63 Correct 1363 ms 102800 KB Output is correct
64 Correct 1410 ms 96520 KB Output is correct
65 Correct 1363 ms 96664 KB Output is correct
66 Correct 13 ms 23816 KB Output is correct
67 Correct 13 ms 23764 KB Output is correct
68 Correct 13 ms 23752 KB Output is correct
69 Correct 63 ms 26424 KB Output is correct
70 Correct 77 ms 31468 KB Output is correct
71 Correct 92 ms 31108 KB Output is correct
72 Correct 101 ms 31236 KB Output is correct
73 Correct 15 ms 24276 KB Output is correct
74 Correct 69 ms 31120 KB Output is correct
75 Correct 66 ms 30948 KB Output is correct
76 Correct 59 ms 30724 KB Output is correct
77 Correct 58 ms 30672 KB Output is correct
78 Correct 76 ms 31068 KB Output is correct
79 Correct 65 ms 30736 KB Output is correct
80 Correct 64 ms 30784 KB Output is correct
81 Correct 1376 ms 105348 KB Output is correct
82 Correct 1307 ms 111780 KB Output is correct
83 Correct 1233 ms 104836 KB Output is correct
84 Correct 984 ms 108780 KB Output is correct
85 Correct 3100 ms 99076 KB Output is correct
86 Correct 3616 ms 103092 KB Output is correct
87 Correct 1417 ms 112864 KB Output is correct
88 Correct 1328 ms 105384 KB Output is correct
89 Correct 1441 ms 101632 KB Output is correct
90 Correct 1361 ms 101492 KB Output is correct
91 Correct 1236 ms 107740 KB Output is correct
92 Correct 1304 ms 103880 KB Output is correct
93 Correct 2141 ms 99056 KB Output is correct
94 Correct 1879 ms 100032 KB Output is correct
95 Correct 1440 ms 98632 KB Output is correct
96 Correct 1325 ms 103932 KB Output is correct
97 Correct 1467 ms 109740 KB Output is correct
98 Correct 1392 ms 109320 KB Output is correct
99 Correct 1442 ms 102616 KB Output is correct
100 Correct 1336 ms 102504 KB Output is correct
101 Correct 1355 ms 104572 KB Output is correct
102 Correct 1231 ms 107284 KB Output is correct
103 Correct 1346 ms 103908 KB Output is correct
104 Execution timed out 6076 ms 113796 KB Time limit exceeded
105 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26316 KB Output is correct
2 Correct 77 ms 31468 KB Output is correct
3 Correct 66 ms 31072 KB Output is correct
4 Correct 93 ms 31224 KB Output is correct
5 Correct 14 ms 24232 KB Output is correct
6 Correct 67 ms 31092 KB Output is correct
7 Correct 58 ms 26336 KB Output is correct
8 Correct 65 ms 31424 KB Output is correct
9 Correct 63 ms 31088 KB Output is correct
10 Correct 95 ms 31148 KB Output is correct
11 Correct 16 ms 24276 KB Output is correct
12 Correct 66 ms 31084 KB Output is correct
13 Correct 58 ms 30840 KB Output is correct
14 Correct 96 ms 30752 KB Output is correct
15 Correct 63 ms 30680 KB Output is correct
16 Correct 71 ms 31164 KB Output is correct
17 Correct 62 ms 30784 KB Output is correct
18 Correct 62 ms 30812 KB Output is correct
19 Correct 58 ms 26392 KB Output is correct
20 Correct 69 ms 31416 KB Output is correct
21 Correct 76 ms 31104 KB Output is correct
22 Correct 94 ms 31180 KB Output is correct
23 Correct 15 ms 24320 KB Output is correct
24 Correct 69 ms 31012 KB Output is correct
25 Correct 58 ms 30784 KB Output is correct
26 Correct 58 ms 30748 KB Output is correct
27 Correct 57 ms 30712 KB Output is correct
28 Correct 69 ms 30924 KB Output is correct
29 Correct 66 ms 30688 KB Output is correct
30 Correct 64 ms 30824 KB Output is correct
31 Correct 1349 ms 99932 KB Output is correct
32 Correct 1317 ms 106328 KB Output is correct
33 Correct 1246 ms 99348 KB Output is correct
34 Correct 958 ms 103260 KB Output is correct
35 Correct 3291 ms 93588 KB Output is correct
36 Correct 3212 ms 102144 KB Output is correct
37 Correct 1460 ms 111600 KB Output is correct
38 Correct 58 ms 26308 KB Output is correct
39 Correct 75 ms 31392 KB Output is correct
40 Correct 71 ms 31060 KB Output is correct
41 Correct 93 ms 31168 KB Output is correct
42 Correct 15 ms 24336 KB Output is correct
43 Correct 75 ms 31016 KB Output is correct
44 Correct 59 ms 30804 KB Output is correct
45 Correct 60 ms 30788 KB Output is correct
46 Correct 61 ms 30692 KB Output is correct
47 Correct 69 ms 30920 KB Output is correct
48 Correct 65 ms 30784 KB Output is correct
49 Correct 63 ms 30888 KB Output is correct
50 Correct 1447 ms 104072 KB Output is correct
51 Correct 1410 ms 110664 KB Output is correct
52 Correct 1303 ms 103496 KB Output is correct
53 Correct 1089 ms 107564 KB Output is correct
54 Correct 3235 ms 97900 KB Output is correct
55 Correct 3475 ms 101864 KB Output is correct
56 Correct 1394 ms 111744 KB Output is correct
57 Correct 2077 ms 174292 KB Output is correct
58 Correct 2634 ms 227756 KB Output is correct
59 Correct 2730 ms 181780 KB Output is correct
60 Correct 991 ms 103660 KB Output is correct
61 Execution timed out 6100 ms 173572 KB Time limit exceeded
62 Halted 0 ms 0 KB -