#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
class edge {
public:
int x, w;
bool dir; // 1 if guards go in this direction
edge(int x, int w, bool d = 0) : x(x), w(w), dir(d) {}
pii pair() {
return pii(x, w);
}
};
bool operator<(const edge &a, const edge &b) {
return pii(a.x, a.w) < pii(b.x, b.w);
}
const int MAXN = 25e4;
const int inf = 1e9;
set<edge> edges[MAXN];
// int prv[MAXN];
// int nxt[MAXN];
int sz[MAXN];
int mod[MAXN];
int dist[MAXN];
int n, m, k;
void prune(int i) {
if (i == n-1 || i == 0 || edges[i].size() != 2) return;
edge l = *edges[i].begin();
edge r = *edges[i].rbegin();
if (sz[i] > 0) {
if (l.dir) swap(l, r);
// nxt[l.x] = r.x;
// prv[r.x] = l.x;
}
edges[i].clear();
edges[l.x].erase(edge(i, l.w));
edges[r.x].erase(edge(i, r.w));
if (l.x != r.x) {
edges[l.x].insert(edge(r.x, l.w+r.w, (sz[i] > 0)));
edges[r.x].insert(edge(l.x, l.w+r.w));
}
prune(l.x);
prune(r.x);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
x--; y--;
edges[x].insert(edge(y, 1));
edges[y].insert(edge(x, 1));
}
cin >> k;
for (int i = 0; i < k; i++) {
int t; cin >> t;
vector<int> v;
for (int j = 0; j < t; j++) {
int x; cin >> x; x--;
v.push_back(x);
}
for (int j = 0; j < t; j++) {
// nxt[v[j]] = v[(j+1)%t];
// prv[v[j]] = v[(j+n-1)%t];
edges[v[j]].erase(edge(v[(j+1)%t], 1));
edges[v[j]].insert(edge(v[(j+1)%t], 1, 1));
sz[v[j]] = v.size();
mod[v[j]] = j;
}
}
for (int i = 0; i < n; i++) {
if (edges[i].size() == 2) prune(i);
}
fill(dist, dist+n, inf);
dist[0] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push(pii(0, 0));
while (!pq.empty()) {
pii t = pq.top();
pq.pop();
int cur = t.second;
if (dist[cur] < t.first) continue;
for (edge p: edges[cur]) {
int nxtval = p.x;
int ndist;
if (sz[cur] == 0) ndist = dist[cur]+p.w;
else if (sz[cur] > 0 && (sz[nxtval] == 0 || p.dir)) {
ndist = dist[cur]+p.w+((dist[cur]%sz[cur])==mod[cur]);
}
else {
if (2*p.w+1 >= sz[cur]) continue;
int req_pos = ((mod[cur]+sz[cur]-2*p.w-1) % sz[cur]);
int cur_pos = (dist[cur] % sz[cur]);
ndist = dist[cur]+p.w + ((req_pos+sz[cur]-cur_pos)-sz[cur]);
}
if (ndist < dist[nxtval]) {
dist[nxtval] = ndist;
pq.push(pii(ndist, nxtval));
}
/*
Case 1: This isn't on a cycle. ez
Case 2: this is on a cycle. add 1 if we arrived right as the watchmen arrived
Case 3: both of these are on the same cycle and the watchmen goes from nxt to cur.
*/
}
}
if (dist[n-1] == inf) cout << "impossible\n";
else cout << dist[n-1] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
22604 KB |
Output is correct |
| 2 |
Incorrect |
96 ms |
31892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
22552 KB |
Output is correct |
| 2 |
Incorrect |
86 ms |
31692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
22552 KB |
Output is correct |
| 2 |
Incorrect |
86 ms |
31692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
22552 KB |
Output is correct |
| 2 |
Incorrect |
86 ms |
31692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
22604 KB |
Output is correct |
| 2 |
Incorrect |
96 ms |
31892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
22604 KB |
Output is correct |
| 2 |
Incorrect |
96 ms |
31892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
22604 KB |
Output is correct |
| 2 |
Incorrect |
96 ms |
31892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
