oj.uz

Submission #729119

# Submission time Handle Problem Language Result Execution time Memory
729119 2023-04-23T14:27:58 Z NeroZein From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 1010 ms 247144 KB 
#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) % v[0].size()] == cur && v[0][sec % v[0].size()] == 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.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 244388 KB Output is correct
2 Incorrect 1004 ms 247144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 244384 KB Output is correct
2 Incorrect 1010 ms 247036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 244384 KB Output is correct
2 Incorrect 1010 ms 247036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 244384 KB Output is correct
2 Incorrect 1010 ms 247036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 244388 KB Output is correct
2 Incorrect 1004 ms 247144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 244388 KB Output is correct
2 Incorrect 1004 ms 247144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 244388 KB Output is correct
2 Incorrect 1004 ms 247144 KB Output isn't correct
3 Halted 0 ms 0 KB -