#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2.5e5 + 11;
const int MAXV = 2750 + 11;
const int MAXC = 1500 + 11;
const int MAXA = 2e6 + 11;
int cyc[MAXN], ci[MAXN], cl[MAXN], vi[MAXN];
vector<int> G[MAXN], H[MAXN];
int dp[MAXN], dp2[MAXV][MAXC];
bool vis[MAXN], vis2[MAXV][MAXC];
vector<pair<int, int>> ch[MAXA];
vector<int> cycles[MAXV];
struct edge{
int u, v;
};
bool in_cycle(int v){
return cyc[v] != 0;
}
int cycle_nxt(int v){
assert(cyc[v] != 0);
return cycles[cyc[v]][(ci[v] + 1) % cl[v]];
}
int cycle_prv(int v){
assert(cyc[v] != 0);
return cycles[cyc[v]][(ci[v] + cl[v] - 1) % cl[v]];
}
int32_t main(){
cin.tie(0); cout.tie(0)->sync_with_stdio(false);
int n, m; cin >> n >> m;
vector<edge> E;
for(int i = 0; i < m; i++){
int u, v; cin >> u >> v;
E.push_back({u, v});
}
int s_cyc = 0;
int k; cin >> k;
for(int i = 0; i < k; i++){
vector<int> v;
int l; cin >> l;
for(int j = 0; j < l; j++){
int u; cin >> u; v.push_back(u);
}
cycles[i + 1] = v;
for(int j = 0; j < l; j++) cyc[v[j]] = i + 1, ci[v[j]] = j, cl[v[j]] = v.size(), vi[v[j]] = 1 + s_cyc + j; s_cyc += l;
}
for(int i = 0; i < m; i++){
edge e = E[i];
if(!in_cycle(e.u)) swap(e.u, e.v);
if(in_cycle(e.u) && in_cycle(e.v)){
if(e.u == cycle_nxt(e.v) || e.u == cycle_prv(e.v))
continue;
H[e.u].push_back(e.v);
H[e.v].push_back(e.u);
}else{
G[e.u].push_back(e.v);
G[e.v].push_back(e.u);
}
}
// for(int i = 1; i <= n; i++) cout << cyc[i] << ' '; cout << endl;
// for(int i = 1; i <= n; i++) cout << ci[i] << ' '; cout << endl;
// for(int i = 1; i <= n; i++) cout << vi[i] << ' '; cout << endl;
memset(dp, 0x3f, sizeof(dp));
memset(dp2, 0x3f, sizeof(dp2));
dp[1] = 0; ch[0].push_back({1, 0});
for(int d = 0; d < MAXA; d++){
for(auto [v, i] : ch[d]){
// printf("dist[(%d %d)] = %d\n", v, i, d);
if(!in_cycle(v)){
assert(i == 0);
if(vis[v]) continue; vis[v] = true;
for(auto u : G[v]){
if(!in_cycle(u)){
if(dp[v] + 1 < dp[u]){
dp[u] = dp[v] + 1;
ch[d + 1].push_back({u, 0});
}
}else{
vector<int> J;
J.push_back(0); J.push_back(1);
J.push_back((((ci[u] - dp[v] + 1) % cl[u]) + cl[u] + 1) % cl[u]);
for(int j : J){
int dst = dp[v] + 1 + j;
if(dst % cl[u] == ci[u]) continue;
if(dst < dp2[vi[u]][dst % cl[u]]){
dp2[vi[u]][dst % cl[u]] = dst;
ch[dst].push_back({u, dst % cl[u]});
}
}
}
}
}else{
if(!vis[v]){
for(int i = 0; i < cl[v]; i++){
dp[v] = min(dp[v], dp2[vi[v]][i]);
}
// printf("dp[%d] = %d\n", v, dp[v]);
vis[v] = true;
for(auto u : G[v]){
assert(!in_cycle(u));
if(dp[v] + 1 < dp[u]){
dp[u] = dp[v] + 1;
ch[d + 1].push_back({u, 0});
}
}
}
assert(d % cl[v] != ci[v]);
if(vis2[vi[v]][d % cl[v]]) continue; vis2[vi[v]][d % cl[v]] = true;
// stationery
if((d + 1) % cl[v] != ci[v] && d + 1 < dp2[vi[v]][(d + 1) % cl[v]]){
dp2[vi[v]][(d + 1) % cl[v]] = d + 1;
ch[d + 1].push_back({v, (d + 1) % cl[v]});
}
for(auto u : H[v]){
for(int j = 0; j < cl[u]; j++){
int dst = d + 1 + j * cl[v];
if(dst % cl[u] != ci[u] && dst < dp2[vi[u]][dst % cl[u]]){
dp2[vi[u]][dst % cl[u]] = dst;
ch[dst].push_back({u, dst % cl[u]});
}
}
}
// forward
int u = cycle_nxt(v);
if(d + 1 < dp2[vi[u]][(d + 1) % cl[u]]){
dp2[vi[u]][(d + 1) % cl[u]] = d + 1;
ch[d + 1].push_back({u, (d + 1) % cl[u]});
}
// backward
u = cycle_prv(v);
if((d + 1) % cl[v] != ci[v] && (d + 2) % cl[v] != ci[v] && d + 1 < dp2[vi[u]][(d + 1) % cl[u]]){
dp2[vi[u]][(d + 1) % cl[u]] = d + 1;
ch[d + 1].push_back({u, (d + 1) % cl[u]});
}
}
}
ch[d].clear();
}
if(dp[n] == 0x3f3f3f3f){
cout << "impossible" << endl;
}else{
cout << dp[n] << endl;
}
}
Compilation message
watchmen.cpp: In function 'int32_t main()':
watchmen.cpp:51:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
51 | for(int j = 0; j < l; j++) cyc[v[j]] = i + 1, ci[v[j]] = j, cl[v[j]] = v.size(), vi[v[j]] = 1 + s_cyc + j; s_cyc += l;
| ^~~
watchmen.cpp:51:110: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
51 | for(int j = 0; j < l; j++) cyc[v[j]] = i + 1, ci[v[j]] = j, cl[v[j]] = v.size(), vi[v[j]] = 1 + s_cyc + j; s_cyc += l;
| ^~~~~
watchmen.cpp:76:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
76 | for(auto [v, i] : ch[d]){
| ^
watchmen.cpp:80:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
80 | if(vis[v]) continue; vis[v] = true;
| ^~
watchmen.cpp:80:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
80 | if(vis[v]) continue; vis[v] = true;
| ^~~
watchmen.cpp:119:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
119 | if(vis2[vi[v]][d % cl[v]]) continue; vis2[vi[v]][d % cl[v]] = true;
| ^~
watchmen.cpp:119:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
119 | if(vis2[vi[v]][d % cl[v]]) continue; vis2[vi[v]][d % cl[v]] = true;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1254 ms |
78288 KB |
Output is correct |
| 2 |
Incorrect |
79 ms |
84932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1253 ms |
78292 KB |
Output is correct |
| 2 |
Incorrect |
81 ms |
84956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1253 ms |
78292 KB |
Output is correct |
| 2 |
Incorrect |
81 ms |
84956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1253 ms |
78292 KB |
Output is correct |
| 2 |
Incorrect |
81 ms |
84956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1254 ms |
78288 KB |
Output is correct |
| 2 |
Incorrect |
79 ms |
84932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1254 ms |
78288 KB |
Output is correct |
| 2 |
Incorrect |
79 ms |
84932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1254 ms |
78288 KB |
Output is correct |
| 2 |
Incorrect |
79 ms |
84932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
