답안 #655697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
655697	2022-11-05T10:26:43 Z	600Mihnea	From Hacks to Snitches (BOI21_watchmen)	C++17	15 / 100	6000 ms	97400 KB

watchmen

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

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	20552 KB	Output is correct
2	Correct	68 ms	25264 KB	Output is correct
3	Correct	60 ms	25080 KB	Output is correct
4	Correct	92 ms	25404 KB	Output is correct
5	Correct	11 ms	18196 KB	Output is correct
6	Correct	74 ms	25152 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	20520 KB	Output is correct
2	Correct	59 ms	25356 KB	Output is correct
3	Correct	76 ms	25072 KB	Output is correct
4	Correct	97 ms	25448 KB	Output is correct
5	Correct	12 ms	18132 KB	Output is correct
6	Correct	68 ms	25080 KB	Output is correct
7	Correct	70 ms	24904 KB	Output is correct
8	Correct	56 ms	24776 KB	Output is correct
9	Correct	61 ms	24852 KB	Output is correct
10	Correct	84 ms	25108 KB	Output is correct
11	Correct	64 ms	24852 KB	Output is correct
12	Correct	79 ms	24808 KB	Output is correct

Subtask #3

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	20520 KB	Output is correct
2	Correct	59 ms	25356 KB	Output is correct
3	Correct	76 ms	25072 KB	Output is correct
4	Correct	97 ms	25448 KB	Output is correct
5	Correct	12 ms	18132 KB	Output is correct
6	Correct	68 ms	25080 KB	Output is correct
7	Correct	70 ms	24904 KB	Output is correct
8	Correct	56 ms	24776 KB	Output is correct
9	Correct	61 ms	24852 KB	Output is correct
10	Correct	84 ms	25108 KB	Output is correct
11	Correct	64 ms	24852 KB	Output is correct
12	Correct	79 ms	24808 KB	Output is correct
13	Correct	88 ms	20544 KB	Output is correct
14	Correct	57 ms	25316 KB	Output is correct
15	Correct	66 ms	25068 KB	Output is correct
16	Correct	111 ms	25404 KB	Output is correct
17	Correct	15 ms	18132 KB	Output is correct
18	Correct	72 ms	25152 KB	Output is correct
19	Correct	57 ms	24820 KB	Output is correct
20	Correct	58 ms	24852 KB	Output is correct
21	Correct	65 ms	24744 KB	Output is correct
22	Correct	92 ms	25100 KB	Output is correct
23	Correct	84 ms	24896 KB	Output is correct
24	Correct	58 ms	24820 KB	Output is correct
25	Correct	1440 ms	90936 KB	Output is correct
26	Correct	1378 ms	97400 KB	Output is correct
27	Correct	1260 ms	90796 KB	Output is correct
28	Correct	1029 ms	94956 KB	Output is correct
29	Execution timed out	6096 ms	86036 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	20520 KB	Output is correct
2	Correct	59 ms	25356 KB	Output is correct
3	Correct	76 ms	25072 KB	Output is correct
4	Correct	97 ms	25448 KB	Output is correct
5	Correct	12 ms	18132 KB	Output is correct
6	Correct	68 ms	25080 KB	Output is correct
7	Correct	70 ms	24904 KB	Output is correct
8	Correct	56 ms	24776 KB	Output is correct
9	Correct	61 ms	24852 KB	Output is correct
10	Correct	84 ms	25108 KB	Output is correct
11	Correct	64 ms	24852 KB	Output is correct
12	Correct	79 ms	24808 KB	Output is correct
13	Correct	88 ms	20544 KB	Output is correct
14	Correct	57 ms	25316 KB	Output is correct
15	Correct	66 ms	25068 KB	Output is correct
16	Correct	111 ms	25404 KB	Output is correct
17	Correct	15 ms	18132 KB	Output is correct
18	Correct	72 ms	25152 KB	Output is correct
19	Correct	57 ms	24820 KB	Output is correct
20	Correct	58 ms	24852 KB	Output is correct
21	Correct	65 ms	24744 KB	Output is correct
22	Correct	92 ms	25100 KB	Output is correct
23	Correct	84 ms	24896 KB	Output is correct
24	Correct	58 ms	24820 KB	Output is correct
25	Correct	1440 ms	90936 KB	Output is correct
26	Correct	1378 ms	97400 KB	Output is correct
27	Correct	1260 ms	90796 KB	Output is correct
28	Correct	1029 ms	94956 KB	Output is correct
29	Execution timed out	6096 ms	86036 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	20552 KB	Output is correct
2	Correct	68 ms	25264 KB	Output is correct
3	Correct	60 ms	25080 KB	Output is correct
4	Correct	92 ms	25404 KB	Output is correct
5	Correct	11 ms	18196 KB	Output is correct
6	Correct	74 ms	25152 KB	Output is correct
7	Correct	87 ms	20520 KB	Output is correct
8	Correct	59 ms	25356 KB	Output is correct
9	Correct	76 ms	25072 KB	Output is correct
10	Correct	97 ms	25448 KB	Output is correct
11	Correct	12 ms	18132 KB	Output is correct
12	Correct	68 ms	25080 KB	Output is correct
13	Correct	70 ms	24904 KB	Output is correct
14	Correct	56 ms	24776 KB	Output is correct
15	Correct	61 ms	24852 KB	Output is correct
16	Correct	84 ms	25108 KB	Output is correct
17	Correct	64 ms	24852 KB	Output is correct
18	Correct	79 ms	24808 KB	Output is correct
19	Correct	10 ms	17876 KB	Output is correct
20	Correct	12 ms	17908 KB	Output is correct
21	Correct	12 ms	17876 KB	Output is correct
22	Correct	88 ms	20448 KB	Output is correct
23	Correct	83 ms	25184 KB	Output is correct
24	Correct	66 ms	25024 KB	Output is correct
25	Correct	91 ms	25344 KB	Output is correct
26	Correct	12 ms	18208 KB	Output is correct
27	Correct	80 ms	24948 KB	Output is correct
28	Correct	63 ms	24768 KB	Output is correct
29	Correct	68 ms	24644 KB	Output is correct
30	Correct	53 ms	24644 KB	Output is correct
31	Correct	79 ms	24980 KB	Output is correct
32	Correct	63 ms	24656 KB	Output is correct
33	Correct	72 ms	24760 KB	Output is correct
34	Correct	1407 ms	91556 KB	Output is correct
35	Correct	1405 ms	87804 KB	Output is correct
36	Correct	1482 ms	87796 KB	Output is correct
37	Incorrect	1298 ms	94112 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	20552 KB	Output is correct
2	Correct	68 ms	25264 KB	Output is correct
3	Correct	60 ms	25080 KB	Output is correct
4	Correct	92 ms	25404 KB	Output is correct
5	Correct	11 ms	18196 KB	Output is correct
6	Correct	74 ms	25152 KB	Output is correct
7	Correct	87 ms	20520 KB	Output is correct
8	Correct	59 ms	25356 KB	Output is correct
9	Correct	76 ms	25072 KB	Output is correct
10	Correct	97 ms	25448 KB	Output is correct
11	Correct	12 ms	18132 KB	Output is correct
12	Correct	68 ms	25080 KB	Output is correct
13	Correct	70 ms	24904 KB	Output is correct
14	Correct	56 ms	24776 KB	Output is correct
15	Correct	61 ms	24852 KB	Output is correct
16	Correct	84 ms	25108 KB	Output is correct
17	Correct	64 ms	24852 KB	Output is correct
18	Correct	79 ms	24808 KB	Output is correct
19	Correct	88 ms	20544 KB	Output is correct
20	Correct	57 ms	25316 KB	Output is correct
21	Correct	66 ms	25068 KB	Output is correct
22	Correct	111 ms	25404 KB	Output is correct
23	Correct	15 ms	18132 KB	Output is correct
24	Correct	72 ms	25152 KB	Output is correct
25	Correct	57 ms	24820 KB	Output is correct
26	Correct	58 ms	24852 KB	Output is correct
27	Correct	65 ms	24744 KB	Output is correct
28	Correct	92 ms	25100 KB	Output is correct
29	Correct	84 ms	24896 KB	Output is correct
30	Correct	58 ms	24820 KB	Output is correct
31	Correct	1440 ms	90936 KB	Output is correct
32	Correct	1378 ms	97400 KB	Output is correct
33	Correct	1260 ms	90796 KB	Output is correct
34	Correct	1029 ms	94956 KB	Output is correct
35	Execution timed out	6096 ms	86036 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-

Subtask #7

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	20552 KB	Output is correct
2	Correct	68 ms	25264 KB	Output is correct
3	Correct	60 ms	25080 KB	Output is correct
4	Correct	92 ms	25404 KB	Output is correct
5	Correct	11 ms	18196 KB	Output is correct
6	Correct	74 ms	25152 KB	Output is correct
7	Correct	87 ms	20520 KB	Output is correct
8	Correct	59 ms	25356 KB	Output is correct
9	Correct	76 ms	25072 KB	Output is correct
10	Correct	97 ms	25448 KB	Output is correct
11	Correct	12 ms	18132 KB	Output is correct
12	Correct	68 ms	25080 KB	Output is correct
13	Correct	70 ms	24904 KB	Output is correct
14	Correct	56 ms	24776 KB	Output is correct
15	Correct	61 ms	24852 KB	Output is correct
16	Correct	84 ms	25108 KB	Output is correct
17	Correct	64 ms	24852 KB	Output is correct
18	Correct	79 ms	24808 KB	Output is correct
19	Correct	88 ms	20544 KB	Output is correct
20	Correct	57 ms	25316 KB	Output is correct
21	Correct	66 ms	25068 KB	Output is correct
22	Correct	111 ms	25404 KB	Output is correct
23	Correct	15 ms	18132 KB	Output is correct
24	Correct	72 ms	25152 KB	Output is correct
25	Correct	57 ms	24820 KB	Output is correct
26	Correct	58 ms	24852 KB	Output is correct
27	Correct	65 ms	24744 KB	Output is correct
28	Correct	92 ms	25100 KB	Output is correct
29	Correct	84 ms	24896 KB	Output is correct
30	Correct	58 ms	24820 KB	Output is correct
31	Correct	1440 ms	90936 KB	Output is correct
32	Correct	1378 ms	97400 KB	Output is correct
33	Correct	1260 ms	90796 KB	Output is correct
34	Correct	1029 ms	94956 KB	Output is correct
35	Execution timed out	6096 ms	86036 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-