제출 #938412

#제출 시각아이디문제언어결과실행 시간메모리
938412Gromp15From Hacks to Snitches (BOI21_watchmen)C++17
15 / 100
6081 ms105844 KiB
#include <bits/stdc++.h> #define ll long long #define ar array #define db double #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rint(l, r) uniform_int_distribution<int>(l, r)(rng) template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } void test_case() { int n, m; cin >> n >> m; vector<vector<int>> adj(n+1); for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } vector<int> size(n+1, 1), who(n+1, -1), id(n+1, -1); int Q; cin >> Q; for (int i = 0; i < Q; i++) { int cur; cin >> cur; for (int j = 0; j < cur; j++) { int x; cin >> x; size[x] = cur; who[x] = j; id[x] = i; } } // if size[v] // then, dist[v] % size[v] != who[v] vector<vector<int>> dist(n+1); for (int i = 1; i <= n; i++) { dist[i].resize(size[i], 1e9); } priority_queue<ar<int, 3>, vector<ar<int, 3>>, greater<ar<int, 3>>> q; dist[1][0] = 0; q.push({0, 1, 0}); auto can_wait = [&](int l, int r, int v) -> bool { if (size[v] == 1) return 1; int L = l % size[v], R = r % size[v]; // L --> R if (L <= R) { return who[v] < L || who[v] > R; } else { return R < who[v] && who[v] < L; } }; while (q.size()) { auto [cost, v, time] = q.top(); q.pop(); if (cost != dist[v][time]) continue; //cout << "V " << v << " " << cost << " " << size[v] << " " << who[v] << '\n'; // if the police is coming through this path, thuen we also can't cross assert(cost % size[v] != who[v]); for (int u : adj[v]) { for (int i = 1; i <= size[u]; i++) { //cout << "Test " << v << " " << u << " " << cost << " " << i << " " << (id[u] != id[v]) << " " << ((who[u] + 1) % size[u] != who[v]) << " " << ((cost + i - 1) % size[u] != who[u]) << endl; if ((cost + i) % size[u] != who[u] && (id[u] != id[v] || ((who[u] + 1) % size[u] != who[v]) || ((cost + i - 1) % size[u] != who[u])) && can_wait(cost, cost + i - 1, v) && ckmin(dist[u][(cost + i) % size[u]], cost + i)) { //cout << "There " << v << " " << u << " " << i << endl; q.push({cost + i, u, (cost + i) % size[u]}); } } } } int ans = *min_element(all(dist[n])); if (ans == 1e9) { cout << "impossible\n"; return; } cout << ans << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while (t--) test_case(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...