Submission #869353

#	Time	Username	Problem	Language	Result	Execution time	Memory
869353		Trisanu_Das	From Hacks to Snitches (BOI21_watchmen)	C++17	100 / 100	1650 ms	120604 KiB

watchmen

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 250000, MAXK = 1000, inf = 1 << 29;
int N, M, K, L[MAXK], r[MAXN], t[MAXN], c[MAXN];
vector<int> e[MAXN], V[MAXK], dp[MAXN];
 
int main() {
  ios_base::sync_with_stdio(false);
  cin >> N >> M;
  for (int i = 0; i < N; i++)
    r[i] = 0, t[i] = -1;
  int u, v;
  for (int i = 0; i < M; i++) {
    cin >> u >> v, u--, v--;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  cin >> K;
  L[0] = 1;
  for (int i = 1; i <= K; i++) {
    cin >> L[i];
    for (int j = 0; j < L[i]; j++) {
      cin >> u, u--;
      V[i].push_back(u);
      r[u] = i;
      t[u] = j;
    }
  }
  for (int i = 0; i < N; i++) {
    dp[i].resize(L[r[i]]);
    for (int j = 0; j < L[r[i]]; j++) dp[i][j] = inf;
  }
  priority_queue<tuple<int, int, int>> pq;
  auto update = [&](int i, int d) {
    int o = d % L[r[i]];
    if (o != t[i] && d < dp[i][o]) dp[i][o] = d, pq.emplace(-d, i, o);
  };
  update(0, 0);
  while (!pq.empty()) {
    auto [d, i, o] = pq.top();
    pq.pop();
    d *= -1;
    if (d != dp[i][o]) continue;
    for (int k = 0; k < (int) e[i].size(); k++) {
      int j = e[i][k];
      if (!r[i] || r[j] != r[i] || (t[j] + 1) % L[r[i]] != t[i] || t[j] != o)  update(j, d + 1);
      if (!r[i] && r[j]) update(j, d + 1 + (t[j] + L[r[j]] - d % L[r[j]]) % L[r[j]]);
      bool re = false;
      if (r[i] && r[j] && (r[j] != r[i] || ((t[j] + 1) % L[r[i]] != t[i] && (t[i] + 1) % L[r[i]] != t[j]))) {
        int tnj = d + (t[j] + L[r[j]] - d % L[r[j]]) % L[r[j]];
        int tnji = tnj + (t[i] + L[r[i]] - tnj % L[r[i]]) % L[r[i]];
        if (tnj != tnji) {
          update(j, tnj + 1);
          re = true;
        } else {
          int nd = tnj + (o + L[r[i]] - t[i]) % L[r[i]];
          update(j, nd + 1);
          if (L[r[j]] % L[r[i]] != 0 && (L[r[i]] % L[r[j]] != 0 || (t[i] + L[r[i]] - o) % L[r[i]] >= L[r[j]])) update(j, nd + 1 + (t[j] + L[r[j]] - nd % L[r[j]]) % L[r[j]]);
        }
      }
      if (!r[i] || !r[j] || re) {
        swap(e[i][k], e[i].back());
        e[i].pop_back();
        k--;
      }
    }
    update(i, d + 1);
  }
  if (dp[N - 1][0] == inf) cout << "impossible\n";
  else cout << dp[N - 1][0] << '\n';
}

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