Submission #526633

#	Time	Username	Problem	Language	Result	Execution time	Memory
526633		xiaowuc1	From Hacks to Snitches (BOI21_watchmen)	C++17	100 / 100	2113 ms	176604 KiB

watchmen

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(1) cerr
// END NO SAD

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

template<class T>
bool updmin(T& a, T b) {
  if(b < a) {
    a = b;
    return true;
  }
  return false;
}
template<class T>
bool updmax(T& a, T b) {
  if(b > a) {
    a = b;
    return true;
  }
  return false;
}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;

void win(int x) {
  cout << x << "\n";
  exit(0);
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n);
  vector<int> cycleidx(n, -1), cyclepos(n, -1);
  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    g[a].pb(b);
    g[b].pb(a);
  }
  int k;
  cin >> k;
  vector<vector<int>> cycles(k);
  for(int i = 0; i < k; i++) {
    int x;
    cin >> x;
    cycles[i].resize(x);
    for(int j = 0; j < x; j++) {
      cin >> cycles[i][j];
      cycleidx[--cycles[i][j]] = i;
      cyclepos[cycles[i][j]] = j;
    }
  }
  vector<vector<int>> dp(n);
  for(int i = 0; i < n; i++) {
    if(cycleidx[i] < 0) dp[i].resize(1);
    else dp[i].resize(sz(cycles[cycleidx[i]]));
    fill(all(dp[i]), 2e9);
  }
  const int THRESH = n + 1000000;
  vector<vector<int>> can(THRESH);
  auto upd = [&](int v, int w) {
    int idx = w % sz(dp[v]);
    if(cyclepos[v] == idx) return;
    if(updmin(dp[v][idx], w)) can[w].pb(v);
  };
  can[0].pb(0); dp[0][0] = 0;
  for(int ret = 0; ret < THRESH; ret++) {
    for(int currv: can[ret]) {
      int idx = ret % sz(dp[currv]);
      if(dp[currv][idx] != ret) continue;
      if(currv == n-1) win(ret);
      for(int eidx = 0; eidx < sz(g[currv]); eidx++) {
        int cand = g[currv][eidx];
        if(cycleidx[currv] < 0 || cycleidx[currv] != cycleidx[cand] || (cyclepos[cand]+1)%sz(dp[currv]) != cyclepos[currv] || cyclepos[cand] != idx) upd(cand, ret+1);
        if(cycleidx[currv] < 0 && cycleidx[cand] >= 0) upd(cand, ret + 1 + (cyclepos[cand] + sz(dp[cand]) - ret % sz(dp[cand])) % sz(dp[cand]));
        bool dead = false;
        if(cycleidx[currv] >= 0 && cycleidx[cand] >= 0 && (cycleidx[currv] != cycleidx[cand] || ((cyclepos[cand]+1) % sz(dp[currv]) != cyclepos[currv] && (cyclepos[currv]+1) % sz(dp[currv]) != cyclepos[cand]))) {
          int fdist = ret + (cyclepos[cand] + sz(dp[cand]) - ret % sz(dp[cand])) % sz(dp[cand]);
          int gdist = fdist + (cyclepos[currv] + sz(dp[currv]) - fdist % sz(dp[currv])) % sz(dp[currv]);
          if(fdist != gdist) {
            upd(cand, fdist+1);
            dead = true;
          }
          else {
            int dist = fdist + (idx + sz(dp[currv]) - cyclepos[currv]) % sz(dp[currv]);
            upd(cand, dist+1);
            if(sz(dp[cand]) % sz(dp[currv]) && (sz(dp[currv]) % sz(dp[cand]) || (cyclepos[currv] + sz(dp[currv]) - idx) % sz(dp[currv]) >= sz(dp[cand]))) {
              upd(cand, dist+1 + (cyclepos[cand] + sz(dp[cand]) - dist % sz(dp[cand])) % sz(dp[cand]));
            }
          }
        }
        if(cycleidx[currv] < 0 || cycleidx[cand] < 0 || dead) {
          if(eidx+1 < sz(g[currv])) swap(g[currv][eidx], g[currv].back());
          g[currv].pop_back();
          eidx--;
        }
      }
      upd(currv, ret+1);
    }
  }
  cout << "impossible\n";
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points
// are you not using modint when you should

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
}

• 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