#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int inf = 1e9+10;
const int maxn = 3e5+10;
const int maxd = 1e7;
int n, m, k;
int szrt[maxn], idrt[maxn], thrt[maxn], isrt[maxn], nxrt[maxn], pvrt[maxn], dlol[maxn];
vector<int> g[maxn], d[maxn];
vector<pair<int,pair<int,int>>> withdist[maxd+1];
int32_t main() {
freopen("in.in", "r", stdin);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u,v; cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
cin >> k;
for(int i = 1; i <= k; i++) {
cin >> szrt[i];
for(int j = 0; j < szrt[i]; j++) {
int v; cin >> v;
idrt[v] = i;
isrt[v] = 1;
thrt[v] = j;
}
}
szrt[0] = 1;
for(int i = 1; i <= n; i++) {
dlol[i] = inf;
if(isrt[i]) {
for(int j = 0; j < szrt[idrt[i]]; j++) {
d[i].pb(inf);
}
int u = i;
for(auto v : g[u]) {
if(isrt[v] && idrt[u] == idrt[v] && thrt[v] == (thrt[u]+1)%szrt[idrt[u]]) {
nxrt[u] = v;
}
if(isrt[v] && idrt[u] == idrt[v] && thrt[u] == (thrt[v]+1)%szrt[idrt[u]]) {
pvrt[u] = v;
}
}
}
else {
d[i].pb(inf);
}
}
d[1][0] = 0;
priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
pq.push(mp(0,mp(1,0)));
withdist[0].pb(mp(0,mp(1,0)));
for(int distcur = 0; distcur <= maxd; distcur++) {
while(withdist[distcur].size()) {
auto X = withdist[distcur].back();
withdist[distcur].pop_back();
int u = X.sc.fr;
int t = X.sc.sc;
int dist = X.fr;
// while(pq.size()) {
// int u = pq.top().sc.fr;
// int t = pq.top().sc.sc;
// int dist = pq.top().fr;
// pq.pop();
if(t != -1 && dist != d[u][t]) continue;
if(t == -1 && dist != dlol[u]) continue;
if(t == -1) {
for(auto v : g[u]) {
if(isrt[v]) {
int d1 = dlol[u]+1;
int t1 = d1%szrt[idrt[v]];
// Vou encontrar o guarda em v ou indo para v
// indo para v == u é depois de v e em t1 ele vai estar em u
if(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u]) && idrt[u] == idrt[v]) continue;
if(d[v][t1] > d1) {
d[v][t1] = d1;
pq.push(mp(d[v][t1],mp(v,t1)));
withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
}
if(idrt[v] != idrt[u]) {
set<int> stt1;
d1 = dlol[u]+1;
while(true) {
int t1 = d1%szrt[idrt[v]];
if(stt1.count(t1)) break;
stt1.insert(t1);
// Vou encontrar o guarda em v ou indo para v
// indo para v == u é depois de v e em t1 ele vai estar em u
if(d[v][t1] > d1 && t1 != thrt[v]) {
d[v][t1] = d1;
pq.push(mp(d[v][t1],mp(v,t1)));
withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
}
d1+= szrt[idrt[u]];
}
}
}
else {
int d1 = dlol[u]+1;
int t1 = 0;
if(d[v][t1] > d1) {
d[v][t1] = d1;
pq.push(mp(d[v][t1],mp(v,t1)));
withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
}
}
}
continue;
}
if(isrt[u]) {
int v,d1,t1;
v = nxrt[u];
d1 = d[u][t]+1;
t1 = d1%szrt[idrt[v]];
// Vou encontrar o guarda em v ou indo para v
// indo para v == u é depois de v e em t1 ele vai estar em u
if(!(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u] && idrt[u] == idrt[v])) && d[v][t1] > d1) {
d[v][t1] = d1;
pq.push(mp(d[v][t1],mp(v,t1)));
withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
}
v = pvrt[u];
d1 = d[u][t]+1;
t1 = d1%szrt[idrt[v]];
// Vou encontrar o guarda em v ou indo para v
// indo para v == u é depois de v e em t1 ele vai estar em u
if(!(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u] && idrt[u] == idrt[v])) && d[v][t1] > d1) {
d[v][t1] = d1;
pq.push(mp(d[v][t1],mp(v,t1)));
withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
}
if(dlol[u] > d[u][t]) {
dlol[u] = d[u][t];
pq.push(mp(dlol[u],mp(u,-1)));
withdist[dlol[u]].pb(mp(dlol[u],mp(u,-1)));
}
v = u;
d1 = d[u][t]+1;
t1 = d1%szrt[idrt[v]];
if(!(t1 == thrt[v]) && d[v][t1] > d1) {
d[v][t1] = d1;
pq.push(mp(d[v][t1],mp(v,t1)));
withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
}
}
else {
for(auto v : g[u]) {
if(isrt[v]) {
// d[u][t]+1+i = (thrt[v]+1) MOD
// i = trrt[v]-d[u][t] MOD
int i = ((thrt[v]-d[u][t])%szrt[idrt[v]]+szrt[idrt[v]])%szrt[idrt[v]];
int d1 = d[u][t]+1+i;
int t1 = d1%szrt[idrt[v]];
if(t1 == thrt[v]) continue;
if(d[v][t1] > d1) {
d[v][t1] = d1;
pq.push(mp(d[v][t1],mp(v,t1)));
withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
}
d1 = d[u][t]+1;
t1 = d1%szrt[idrt[v]];
if(t1 == thrt[v]) continue;
if(d[v][t1] > d1) {
d[v][t1] = d1;
pq.push(mp(d[v][t1],mp(v,t1)));
withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
}
}
else {
int d1 = d[u][t]+1;
int t1 = 0;
if(d[v][t1] > d1) {
d[v][t1] = d1;
pq.push(mp(d[v][t1],mp(v,t1)));
withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
}
}
}
}
}
}
if(d[n][0] == inf) cout << "impossible" << endl;
else cout << d[n][0] << endl;
}
Compilation message
watchmen.cpp: In function 'int32_t main()':
watchmen.cpp:90:97: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
90 | if(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u]) && idrt[u] == idrt[v]) continue;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
watchmen.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen("in.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
433 ms |
500836 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
352 ms |
505204 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
352 ms |
505204 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
352 ms |
505204 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
433 ms |
500836 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
433 ms |
500836 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
433 ms |
500836 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
