oj.uz

Submission #850664

# Submission time Handle Problem Language Result Execution time Memory
850664 2023-09-17T08:50:22 Z d4xn From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 1643 ms 58072 KB 
#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)) 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 10496 KB Output is correct
2 Incorrect 1643 ms 58072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 10420 KB Output is correct
2 Incorrect 1642 ms 57940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 10420 KB Output is correct
2 Incorrect 1642 ms 57940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 10420 KB Output is correct
2 Incorrect 1642 ms 57940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 10496 KB Output is correct
2 Incorrect 1643 ms 58072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 10496 KB Output is correct
2 Incorrect 1643 ms 58072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 10496 KB Output is correct
2 Incorrect 1643 ms 58072 KB Output isn't correct
3 Halted 0 ms 0 KB -