Submission #655836

#	Time	Username	Problem	Language	Result	Execution time	Memory
655836		600Mihnea	From Hacks to Snitches (BOI21_watchmen)	C++17	50 / 100	6086 ms	239152 KiB

watchmen

// 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];
int maxd;
const int D = 3000;
vector<int> q[D];

priority_queue<pair<int, int>> pq;

void relax(int id, int d) {
  if (d < dp[id]) {
    dp[id] = d;
    q[d % D].push_back(id);
    maxd = max(maxd, d);
  }
}
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";
  }

  relax(single_vertex_id[1], 0);

  for (int cd = 0; cd <= maxd; cd++) {
    while (!q[cd % D].empty()) {
      int idv = q[cd % D].back(), d = cd;
      q[cd % D].pop_back();
      if (dp[idv] != d) {
        continue;
      }
      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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 25 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20