제출 #655735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
655735		600Mihnea	From Hacks to Snitches (BOI21_watchmen)	C++17	40 / 100	6047 ms	104524 KiB

watchmen

// pana la ora 1
bool home = 0;
bool verbose = 1;

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

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) };
      }
    }
  }
  if (verbose) {
    cout << "y = " << y << "\n";
    cout << "################################################################################### \n";
  }



  map<pair<int, int>, int> spec;
  vector<pair<int, int>> all;

  for (int vertex = 1; vertex <= n; vertex++) {
    if (int cycle = cycle_id[vertex]) {
      for (auto& vecin : g[vertex]) {
        if (int cycle_vecin = cycle_id[vecin]) {
          // vecin is on a cycle
          if (cycle_vecin != cycle) {
            // vecin is on a different cycle
            spec[{vertex, vecin}] = 0;
          }
        }
      }
    }
  }
  vector<vector<int>> ids;
  for (auto& it : spec) {
    it.second = (int)all.size();
    all.push_back(it.first);
    int vertex = it.first.first, vecin = it.first.second;
    int l_vecin = cycles[cycle_id[vecin]].size();
    ids.push_back({});
    ids.back().resize(l_vecin);
    for (int r = 0; r < l_vecin; r++) {
      y++;
      ids.back()[r] = y;
      what[y] = { -(int)ids.size(), r };
    }
  }

  for (int i = 1; i <= y; i++) {
    dp[i] = INF;
  }
  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 (vertex < 0) {
    //  cout << "aici\n";
      int p = vertex;
      p *= -1;
      p--;
      assert(0 <= p && p < (int)ids.size());
      int vertex = all[p].first, vecin = all[p].second;
      int l = cycles[cycle_id[vertex]].size();
      int l_vecin = cycles[cycle_id[vecin]].size();
      assert((int)ids[p].size() == l_vecin);
      relax(ids[p][(d + l) % l_vecin], d + l);

      if (d % l_vecin == cycle_location[vecin]) {
        continue;
      }
      relax(cycle_vertex_id[vecin][d % l_vecin], d);
      continue;
    }
    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
            assert(spec.count({ vertex, vecin }));
            int p = spec[{vertex, vecin}];
          //  cout << "gest:" << (int)pq.size()<<" "<< ids[p][(d + 1) % l_vecin]<< " vs "<<1<<"..."<<y << "\n";
            relax(ids[p][(d + 1) % l_vecin], d + 1);
            continue;
            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;
}

컴파일 시 표준 에러 (stderr) 메시지

watchmen.cpp: In function 'int main()':
watchmen.cpp:138:9: warning: unused variable 'vertex' [-Wunused-variable]
  138 |     int vertex = it.first.first, vecin = it.first.second;
      |         ^~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 25 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20