Submission #729117

#	Time	Username	Problem	Language	Result	Execution time	Memory
729117		NeroZein	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	927 ms	247504 KiB

watchmen

#include<bits/stdc++.h>
using namespace std;

const int N = 300005;
const int X = 201;

vector<int> g[N]; 

bool a[N][X];
int cost[N][X];

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); 
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u); 
  }
  int k;
  cin >> k;
  vector<vector<int>> v(k); 
  for (int i = 0; i < k; ++i) {
    int l;
    cin >> l;
    v[i].resize(l); 
    for (int j = 0; j < l; ++j) {
      cin >> v[i][j];
    }
    for (int j = 0; j < X; ++j) {
      a[v[i][j % l]][j] = true; 
    }
  }
  for (int i = 1; i <= n; ++i) {
    g[i].push_back(i); 
  }
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < X; ++j) {
      cost[i][j] = INT_MAX;
    }
  }
  //cout << a[2][2] << '\n';
  queue<pair<int, int>> que;
  que.emplace(1, 0); 
  cost[1][0] = 0;
  while (!que.empty()) {
    auto [cur, sec] = que.front();
    que.pop();
    //cout << cur << ' ' << sec << '\n'; 
    //cout << "us: ";
    for (int u : g[cur]) {
      if (!a[u][(sec + 1) % X] && !(v[0][(sec + 1) % X] == cur && v[0][sec] == u) && cost[cur][sec] + 1 < cost[u][(sec + 1) % X]) {
        cost[u][(sec + 1) % X] = cost[cur][sec] + 1; 
        //cout << u << ' '; 
        que.emplace(u, (sec + 1) % X); 
      }
    }
    //cout << '\n'; 
  }
  //for (int i = 1; i <= n; ++i) {
    //for (int j = 0; j < X; ++j) {
      //cout << cost[i][j] << " ";
    //}
    //cout << '\n'; 
  //}
  int ans = INT_MAX;
  for (int i = 0; i < X; ++i) {
    ans = min(ans, cost[n][i]);
  }
  if (ans == INT_MAX) {
    cout << "impossible" << '\n'; 
  } else {
    cout << ans << '\n';
  }
}

• Subtask 1: 0 / 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