#include <bits/stdc++.h>
using namespace std;
#define mnto(x, y) x = min(x, (__typeof__(x)) y)
#define mxto(x, y) x = max(x, (__typeof__(x)) y)
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ii> vii;
#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 200005
#define MAXK 1000
#define MAXL 1505
struct edge {
int v;
vii res;
edge() {}
edge(int v): v(v) {}
};
int n, m;
vector<edge> adj[MAXN];
int k;
int l[MAXK];
int arr[MAXK][MAXL];
edge inv[MAXN];
priority_queue<pll, vector<pll>, greater<pll>> pq;
ll dist[MAXN];
int main() {
scanf("%d%d", &n, &m);
REP (i, 0, m) {
int u, v; scanf("%d%d", &u, &v);
adj[u].pb(edge(v));
adj[v].pb(edge(u));
}
scanf("%d", &k);
REP (i, 0, k) {
scanf("%d", &l[i]);
REP (j, 0, l[i]) {
scanf("%d", &arr[i][j]);
}
REP (j, 0, l[i]) {
int v = arr[i][j], u = arr[i][(j + 1) % l[i]];
for (edge &e : adj[u]) {
if (e.v == v) {
e.res.pb(l[i], j);
}
}
inv[v] = edge();
inv[v].res.pb(l[i], j);
}
}
REP (i, 1, n + 1) {
dist[i] = LINF;
}
dist[1] = 0;
pq.push(MP(0, 1));
while (!pq.empty()) {
auto [ud, u] = pq.top(); pq.pop();
if (dist[u] != ud) continue;
for (edge e : adj[u]) {
bool pos = 1;
for (auto [mod, rem] : e.res) {
if (ud % mod == rem) pos = 0;
}
if (!pos) continue;
ll vd = ud + 1;
bool poss = 1;
for (auto [mod, rem] : inv[e.v].res) {
if ((ud + 1) % mod == rem) poss = 0;
}
if (!poss) {
bool posss = 1;
for (auto [mod, rem] : inv[u].res) {
if ((ud + 1) % mod == rem) posss = 0;
}
if (posss) vd = ud + 1;
else vd = LINF;
}
if (vd < dist[e.v]) {
dist[e.v] = vd;
pq.push(MP(vd, e.v));
}
}
}
if (dist[n] == LINF) {
printf("impossible\n");
} else {
printf("%lld\n", dist[n]);
}
return 0;
}
Compilation message
watchmen.cpp: In function 'int main()':
watchmen.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
watchmen.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | int u, v; scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
watchmen.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
watchmen.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d", &l[i]);
| ~~~~~^~~~~~~~~~~~~
watchmen.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d", &arr[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~
watchmen.cpp:29:8: warning: '<anonymous>.edge::v' may be used uninitialized in this function [-Wmaybe-uninitialized]
29 | struct edge {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
18944 KB |
Output is correct |
| 2 |
Incorrect |
85 ms |
21692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
18932 KB |
Output is correct |
| 2 |
Incorrect |
88 ms |
21668 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
18932 KB |
Output is correct |
| 2 |
Incorrect |
88 ms |
21668 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
18932 KB |
Output is correct |
| 2 |
Incorrect |
88 ms |
21668 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
18944 KB |
Output is correct |
| 2 |
Incorrect |
85 ms |
21692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
18944 KB |
Output is correct |
| 2 |
Incorrect |
85 ms |
21692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
18944 KB |
Output is correct |
| 2 |
Incorrect |
85 ms |
21692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
