oj.uz

Submission #655711

# Submission time Handle Problem Language Result Execution time Memory
655711 2022-11-05T10:57:05 Z 600Mihnea From Hacks to Snitches (BOI21_watchmen) C++17
50 / 100
 6000 ms 178680 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];
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() {

    verbose = 0;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


  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());
      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";
  }

  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) {
      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
      */

      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);
            }
          }
        }
      }
    }
  }

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

Compilation message

watchmen.cpp: In function 'int main()':
watchmen.cpp:117:9: warning: unused variable 'r' [-Wunused-variable]
  117 |     int r = what[idv].r;
      |         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 20552 KB Output is correct
2 Correct 78 ms 25316 KB Output is correct
3 Correct 81 ms 25080 KB Output is correct
4 Correct 97 ms 25376 KB Output is correct
5 Correct 12 ms 18132 KB Output is correct
6 Correct 59 ms 25112 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 20520 KB Output is correct
2 Correct 58 ms 25280 KB Output is correct
3 Correct 58 ms 25156 KB Output is correct
4 Correct 95 ms 25408 KB Output is correct
5 Correct 11 ms 18208 KB Output is correct
6 Correct 58 ms 25084 KB Output is correct
7 Correct 57 ms 24820 KB Output is correct
8 Correct 54 ms 24780 KB Output is correct
9 Correct 64 ms 24824 KB Output is correct
10 Correct 69 ms 25080 KB Output is correct
11 Correct 58 ms 24908 KB Output is correct
12 Correct 60 ms 24904 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 20520 KB Output is correct
2 Correct 58 ms 25280 KB Output is correct
3 Correct 58 ms 25156 KB Output is correct
4 Correct 95 ms 25408 KB Output is correct
5 Correct 11 ms 18208 KB Output is correct
6 Correct 58 ms 25084 KB Output is correct
7 Correct 57 ms 24820 KB Output is correct
8 Correct 54 ms 24780 KB Output is correct
9 Correct 64 ms 24824 KB Output is correct
10 Correct 69 ms 25080 KB Output is correct
11 Correct 58 ms 24908 KB Output is correct
12 Correct 60 ms 24904 KB Output is correct
13 Correct 75 ms 20480 KB Output is correct
14 Correct 57 ms 25372 KB Output is correct
15 Correct 56 ms 25148 KB Output is correct
16 Correct 91 ms 25436 KB Output is correct
17 Correct 11 ms 18204 KB Output is correct
18 Correct 65 ms 25080 KB Output is correct
19 Correct 59 ms 24856 KB Output is correct
20 Correct 58 ms 24848 KB Output is correct
21 Correct 55 ms 24784 KB Output is correct
22 Correct 67 ms 25116 KB Output is correct
23 Correct 63 ms 24844 KB Output is correct
24 Correct 61 ms 24896 KB Output is correct
25 Correct 1285 ms 91128 KB Output is correct
26 Correct 1301 ms 97492 KB Output is correct
27 Correct 1340 ms 91100 KB Output is correct
28 Correct 1000 ms 95480 KB Output is correct
29 Correct 5041 ms 86256 KB Output is correct
30 Correct 5481 ms 95328 KB Output is correct
31 Correct 1449 ms 103584 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 20520 KB Output is correct
2 Correct 58 ms 25280 KB Output is correct
3 Correct 58 ms 25156 KB Output is correct
4 Correct 95 ms 25408 KB Output is correct
5 Correct 11 ms 18208 KB Output is correct
6 Correct 58 ms 25084 KB Output is correct
7 Correct 57 ms 24820 KB Output is correct
8 Correct 54 ms 24780 KB Output is correct
9 Correct 64 ms 24824 KB Output is correct
10 Correct 69 ms 25080 KB Output is correct
11 Correct 58 ms 24908 KB Output is correct
12 Correct 60 ms 24904 KB Output is correct
13 Correct 75 ms 20480 KB Output is correct
14 Correct 57 ms 25372 KB Output is correct
15 Correct 56 ms 25148 KB Output is correct
16 Correct 91 ms 25436 KB Output is correct
17 Correct 11 ms 18204 KB Output is correct
18 Correct 65 ms 25080 KB Output is correct
19 Correct 59 ms 24856 KB Output is correct
20 Correct 58 ms 24848 KB Output is correct
21 Correct 55 ms 24784 KB Output is correct
22 Correct 67 ms 25116 KB Output is correct
23 Correct 63 ms 24844 KB Output is correct
24 Correct 61 ms 24896 KB Output is correct
25 Correct 1285 ms 91128 KB Output is correct
26 Correct 1301 ms 97492 KB Output is correct
27 Correct 1340 ms 91100 KB Output is correct
28 Correct 1000 ms 95480 KB Output is correct
29 Correct 5041 ms 86256 KB Output is correct
30 Correct 5481 ms 95328 KB Output is correct
31 Correct 1449 ms 103584 KB Output is correct
32 Correct 78 ms 20544 KB Output is correct
33 Correct 64 ms 25388 KB Output is correct
34 Correct 65 ms 25152 KB Output is correct
35 Correct 90 ms 25512 KB Output is correct
36 Correct 12 ms 18108 KB Output is correct
37 Correct 64 ms 25128 KB Output is correct
38 Correct 59 ms 24840 KB Output is correct
39 Correct 60 ms 24852 KB Output is correct
40 Correct 58 ms 24800 KB Output is correct
41 Correct 75 ms 25056 KB Output is correct
42 Correct 61 ms 24792 KB Output is correct
43 Correct 60 ms 24820 KB Output is correct
44 Correct 1369 ms 96436 KB Output is correct
45 Correct 1361 ms 103052 KB Output is correct
46 Correct 1302 ms 96516 KB Output is correct
47 Correct 995 ms 100420 KB Output is correct
48 Correct 5400 ms 91540 KB Output is correct
49 Correct 5424 ms 95628 KB Output is correct
50 Correct 1472 ms 103708 KB Output is correct
51 Correct 2127 ms 131972 KB Output is correct
52 Correct 2588 ms 162180 KB Output is correct
53 Correct 2252 ms 149156 KB Output is correct
54 Correct 1016 ms 93184 KB Output is correct
55 Execution timed out 6029 ms 178680 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 20552 KB Output is correct
2 Correct 78 ms 25316 KB Output is correct
3 Correct 81 ms 25080 KB Output is correct
4 Correct 97 ms 25376 KB Output is correct
5 Correct 12 ms 18132 KB Output is correct
6 Correct 59 ms 25112 KB Output is correct
7 Correct 73 ms 20520 KB Output is correct
8 Correct 58 ms 25280 KB Output is correct
9 Correct 58 ms 25156 KB Output is correct
10 Correct 95 ms 25408 KB Output is correct
11 Correct 11 ms 18208 KB Output is correct
12 Correct 58 ms 25084 KB Output is correct
13 Correct 57 ms 24820 KB Output is correct
14 Correct 54 ms 24780 KB Output is correct
15 Correct 64 ms 24824 KB Output is correct
16 Correct 69 ms 25080 KB Output is correct
17 Correct 58 ms 24908 KB Output is correct
18 Correct 60 ms 24904 KB Output is correct
19 Correct 9 ms 17876 KB Output is correct
20 Correct 11 ms 17876 KB Output is correct
21 Correct 11 ms 17876 KB Output is correct
22 Correct 76 ms 20552 KB Output is correct
23 Correct 61 ms 25380 KB Output is correct
24 Correct 64 ms 25076 KB Output is correct
25 Correct 93 ms 25424 KB Output is correct
26 Correct 11 ms 18132 KB Output is correct
27 Correct 62 ms 25116 KB Output is correct
28 Correct 57 ms 24816 KB Output is correct
29 Correct 60 ms 24768 KB Output is correct
30 Correct 58 ms 24744 KB Output is correct
31 Correct 71 ms 25024 KB Output is correct
32 Correct 60 ms 24768 KB Output is correct
33 Correct 58 ms 24896 KB Output is correct
34 Correct 1402 ms 91660 KB Output is correct
35 Correct 1459 ms 88084 KB Output is correct
36 Correct 1455 ms 87996 KB Output is correct
37 Correct 1299 ms 94292 KB Output is correct
38 Correct 1410 ms 90728 KB Output is correct
39 Correct 3493 ms 86600 KB Output is correct
40 Correct 2637 ms 86892 KB Output is correct
41 Correct 1840 ms 85612 KB Output is correct
42 Correct 1389 ms 90760 KB Output is correct
43 Correct 1452 ms 96756 KB Output is correct
44 Correct 1444 ms 96944 KB Output is correct
45 Correct 1489 ms 90676 KB Output is correct
46 Correct 1386 ms 90736 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 20552 KB Output is correct
2 Correct 78 ms 25316 KB Output is correct
3 Correct 81 ms 25080 KB Output is correct
4 Correct 97 ms 25376 KB Output is correct
5 Correct 12 ms 18132 KB Output is correct
6 Correct 59 ms 25112 KB Output is correct
7 Correct 73 ms 20520 KB Output is correct
8 Correct 58 ms 25280 KB Output is correct
9 Correct 58 ms 25156 KB Output is correct
10 Correct 95 ms 25408 KB Output is correct
11 Correct 11 ms 18208 KB Output is correct
12 Correct 58 ms 25084 KB Output is correct
13 Correct 57 ms 24820 KB Output is correct
14 Correct 54 ms 24780 KB Output is correct
15 Correct 64 ms 24824 KB Output is correct
16 Correct 69 ms 25080 KB Output is correct
17 Correct 58 ms 24908 KB Output is correct
18 Correct 60 ms 24904 KB Output is correct
19 Correct 75 ms 20480 KB Output is correct
20 Correct 57 ms 25372 KB Output is correct
21 Correct 56 ms 25148 KB Output is correct
22 Correct 91 ms 25436 KB Output is correct
23 Correct 11 ms 18204 KB Output is correct
24 Correct 65 ms 25080 KB Output is correct
25 Correct 59 ms 24856 KB Output is correct
26 Correct 58 ms 24848 KB Output is correct
27 Correct 55 ms 24784 KB Output is correct
28 Correct 67 ms 25116 KB Output is correct
29 Correct 63 ms 24844 KB Output is correct
30 Correct 61 ms 24896 KB Output is correct
31 Correct 1285 ms 91128 KB Output is correct
32 Correct 1301 ms 97492 KB Output is correct
33 Correct 1340 ms 91100 KB Output is correct
34 Correct 1000 ms 95480 KB Output is correct
35 Correct 5041 ms 86256 KB Output is correct
36 Correct 5481 ms 95328 KB Output is correct
37 Correct 1449 ms 103584 KB Output is correct
38 Correct 9 ms 17876 KB Output is correct
39 Correct 11 ms 17876 KB Output is correct
40 Correct 11 ms 17876 KB Output is correct
41 Correct 76 ms 20552 KB Output is correct
42 Correct 61 ms 25380 KB Output is correct
43 Correct 64 ms 25076 KB Output is correct
44 Correct 93 ms 25424 KB Output is correct
45 Correct 11 ms 18132 KB Output is correct
46 Correct 62 ms 25116 KB Output is correct
47 Correct 57 ms 24816 KB Output is correct
48 Correct 60 ms 24768 KB Output is correct
49 Correct 58 ms 24744 KB Output is correct
50 Correct 71 ms 25024 KB Output is correct
51 Correct 60 ms 24768 KB Output is correct
52 Correct 58 ms 24896 KB Output is correct
53 Correct 1402 ms 91660 KB Output is correct
54 Correct 1459 ms 88084 KB Output is correct
55 Correct 1455 ms 87996 KB Output is correct
56 Correct 1299 ms 94292 KB Output is correct
57 Correct 1410 ms 90728 KB Output is correct
58 Correct 3493 ms 86600 KB Output is correct
59 Correct 2637 ms 86892 KB Output is correct
60 Correct 1840 ms 85612 KB Output is correct
61 Correct 1389 ms 90760 KB Output is correct
62 Correct 1452 ms 96756 KB Output is correct
63 Correct 1444 ms 96944 KB Output is correct
64 Correct 1489 ms 90676 KB Output is correct
65 Correct 1386 ms 90736 KB Output is correct
66 Correct 10 ms 17876 KB Output is correct
67 Correct 10 ms 17876 KB Output is correct
68 Correct 10 ms 17864 KB Output is correct
69 Correct 76 ms 20432 KB Output is correct
70 Correct 63 ms 25384 KB Output is correct
71 Correct 64 ms 25148 KB Output is correct
72 Correct 93 ms 25384 KB Output is correct
73 Correct 12 ms 18172 KB Output is correct
74 Correct 63 ms 25252 KB Output is correct
75 Correct 62 ms 24892 KB Output is correct
76 Correct 59 ms 24860 KB Output is correct
77 Correct 60 ms 24732 KB Output is correct
78 Correct 71 ms 25052 KB Output is correct
79 Correct 65 ms 24804 KB Output is correct
80 Correct 64 ms 24840 KB Output is correct
81 Correct 1376 ms 97896 KB Output is correct
82 Correct 1318 ms 104276 KB Output is correct
83 Correct 1254 ms 97704 KB Output is correct
84 Correct 989 ms 101896 KB Output is correct
85 Correct 4993 ms 93136 KB Output is correct
86 Correct 5274 ms 96676 KB Output is correct
87 Correct 1467 ms 104776 KB Output is correct
88 Correct 1398 ms 98340 KB Output is correct
89 Correct 1457 ms 94600 KB Output is correct
90 Correct 1468 ms 94420 KB Output is correct
91 Correct 1296 ms 100948 KB Output is correct
92 Correct 1380 ms 97032 KB Output is correct
93 Correct 3464 ms 93112 KB Output is correct
94 Correct 2580 ms 93020 KB Output is correct
95 Correct 1743 ms 91540 KB Output is correct
96 Correct 1379 ms 97056 KB Output is correct
97 Correct 1405 ms 102808 KB Output is correct
98 Correct 1409 ms 102348 KB Output is correct
99 Correct 1475 ms 95604 KB Output is correct
100 Correct 1376 ms 95488 KB Output is correct
101 Correct 1367 ms 97164 KB Output is correct
102 Correct 1271 ms 99808 KB Output is correct
103 Correct 1390 ms 95892 KB Output is correct
104 Execution timed out 6008 ms 94600 KB Time limit exceeded
105 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 20552 KB Output is correct
2 Correct 78 ms 25316 KB Output is correct
3 Correct 81 ms 25080 KB Output is correct
4 Correct 97 ms 25376 KB Output is correct
5 Correct 12 ms 18132 KB Output is correct
6 Correct 59 ms 25112 KB Output is correct
7 Correct 73 ms 20520 KB Output is correct
8 Correct 58 ms 25280 KB Output is correct
9 Correct 58 ms 25156 KB Output is correct
10 Correct 95 ms 25408 KB Output is correct
11 Correct 11 ms 18208 KB Output is correct
12 Correct 58 ms 25084 KB Output is correct
13 Correct 57 ms 24820 KB Output is correct
14 Correct 54 ms 24780 KB Output is correct
15 Correct 64 ms 24824 KB Output is correct
16 Correct 69 ms 25080 KB Output is correct
17 Correct 58 ms 24908 KB Output is correct
18 Correct 60 ms 24904 KB Output is correct
19 Correct 75 ms 20480 KB Output is correct
20 Correct 57 ms 25372 KB Output is correct
21 Correct 56 ms 25148 KB Output is correct
22 Correct 91 ms 25436 KB Output is correct
23 Correct 11 ms 18204 KB Output is correct
24 Correct 65 ms 25080 KB Output is correct
25 Correct 59 ms 24856 KB Output is correct
26 Correct 58 ms 24848 KB Output is correct
27 Correct 55 ms 24784 KB Output is correct
28 Correct 67 ms 25116 KB Output is correct
29 Correct 63 ms 24844 KB Output is correct
30 Correct 61 ms 24896 KB Output is correct
31 Correct 1285 ms 91128 KB Output is correct
32 Correct 1301 ms 97492 KB Output is correct
33 Correct 1340 ms 91100 KB Output is correct
34 Correct 1000 ms 95480 KB Output is correct
35 Correct 5041 ms 86256 KB Output is correct
36 Correct 5481 ms 95328 KB Output is correct
37 Correct 1449 ms 103584 KB Output is correct
38 Correct 78 ms 20544 KB Output is correct
39 Correct 64 ms 25388 KB Output is correct
40 Correct 65 ms 25152 KB Output is correct
41 Correct 90 ms 25512 KB Output is correct
42 Correct 12 ms 18108 KB Output is correct
43 Correct 64 ms 25128 KB Output is correct
44 Correct 59 ms 24840 KB Output is correct
45 Correct 60 ms 24852 KB Output is correct
46 Correct 58 ms 24800 KB Output is correct
47 Correct 75 ms 25056 KB Output is correct
48 Correct 61 ms 24792 KB Output is correct
49 Correct 60 ms 24820 KB Output is correct
50 Correct 1369 ms 96436 KB Output is correct
51 Correct 1361 ms 103052 KB Output is correct
52 Correct 1302 ms 96516 KB Output is correct
53 Correct 995 ms 100420 KB Output is correct
54 Correct 5400 ms 91540 KB Output is correct
55 Correct 5424 ms 95628 KB Output is correct
56 Correct 1472 ms 103708 KB Output is correct
57 Correct 2127 ms 131972 KB Output is correct
58 Correct 2588 ms 162180 KB Output is correct
59 Correct 2252 ms 149156 KB Output is correct
60 Correct 1016 ms 93184 KB Output is correct
61 Execution timed out 6029 ms 178680 KB Time limit exceeded
62 Halted 0 ms 0 KB -