Submission #850665

#	Time	Username	Problem	Language	Result	Execution time	Memory
850665		d4xn	From Hacks to Snitches (BOI21_watchmen)	C++17	5 / 100	1580 ms	524288 KiB

watchmen

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define tp3 tuple<int, int, int>

const int N = 1e5 + 1, K = 2750 + 1, inf = INT_MAX;

int n, m, k, Lcm, copId[N];
vector<int> adj[N], cop[N];
vector<vector<int>> dp;

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  memset(copId, -1, sizeof(copId));
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  for (int i = 0; i < n; i++) {
    adj[i].push_back(i);
  }

  cin >> k;
  Lcm = 1;
  for (int i = 0; i < k; i++) {
    int x;
    cin >> x;
    Lcm = min(n + K, lcm(Lcm, x));

    cop[i].resize(x);
    for (int& j : cop[i]) {
      cin >> j;
      j--;
      copId[j] = i;
    }
  }
  dp.resize(Lcm, vector<int>(n, inf));
  
  queue<tp3> q;
  q.push(make_tuple(0, 0, 0)); // {dis, sec, node}
  while (!q.empty()) {
    int d = get<0>(q.front());
    int s = get<1>(q.front());
    int u = get<2>(q.front());
    q.pop();

    if (!(rand() % K) && d > n) continue;

    if (copId[u] != -1) {
      int x = copId[u];
      if (cop[x][s % cop[x].size()] == u) continue;
    }

    if (dp[s][u] <= d) continue;
    dp[s][u] = d;

    for (int& v : adj[u]) {
      int nwSec = (s+1) % Lcm;

      if (copId[v] != -1) {
        int x = copId[v];
        if (cop[x][s] == v && cop[x][(s+1) % cop[x].size()] == u) {
          // no puedo ir a este nodo
        }
        else {
          if (dp[nwSec][v] > d+1) q.push(make_tuple(d+1, nwSec, v));
        }
      }
      else {
        if (dp[nwSec][v] > d+1) q.push(make_tuple(d+1, nwSec, v));
      }
    }
  }

  int ans = inf;
  for (int i = 0; i < Lcm; i++) {
    ans = min(ans, dp[i][n-1]);
  }

  if (ans == inf) cout << "impossible\n";
  else cout << ans << "\n";
}

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