#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
typedef pair <int, int> pi;
const int MAXN = 250005;
const llint INF = 1000000000000000000LL;
int n, m, k;
int d[MAXN], ost[MAXN], koji[MAXN], special[MAXN];
llint best[MAXN], dist[3005][3005];
bool bio[3005][3005];
vector <pi> edges;
bool watched[MAXN];
vector <int> good, bad, sus_good[MAXN], sus_bad[MAXN];
void ispis () {
cout << "good" << endl;
for (auto x : good) {
cout << x << ": ";
for (auto sus : sus_good[x]) cout << sus << " ";
cout << "| ";
for (auto sus : sus_bad[x]) cout << sus << " ";
cout << endl;
}
cout << "bad" << endl;
for (auto x : bad) {
cout << x << ": ";
for (auto sus : sus_good[x]) cout << sus << " ";
cout << "| ";
for (auto sus : sus_bad[x]) cout << sus << " ";
cout << endl;
}
}
void build () {
for (int i = 1; i <= n; i++) {
if (watched[i]) bad.push_back(i); else good.push_back(i);
}
for (int i = 0; i < bad.size(); i++) {
koji[bad[i]] = i;
}
for (auto pp : edges) {
int a = pp.first, b = pp.second;
if (watched[b]) sus_bad[a].push_back(b); else sus_good[a].push_back(b);
if (watched[a]) sus_bad[b].push_back(a); else sus_good[b].push_back(a);
}
}
priority_queue < pair <llint, pi> > pq;
void dijkstra () {
for (int i = 1; i <= n; i++) {
best[i] = INF;
}
for (int i = 0; i < bad.size(); i++) {
int node = bad[i];
for (int j = 0; j < d[node]; j++) {
dist[i][j] = INF;
}
}
best[1] = 0;
pq.push({0, {-1, 1}});
while (!pq.empty()) {
llint pq_dist = -pq.top().first;
int jen = pq.top().second.first;
int dva = pq.top().second.second;
pq.pop();
int node;
if (jen == -1) {
node = dva;
if (pq_dist > best[node]) continue;
} else {
node = bad[jen];
if (pq_dist > dist[jen][dva]) continue;
}
if (!watched[node]) {
for (auto sus : sus_good[node]) {
llint novi = best[node] + 1;
if (novi < best[sus]) {
best[sus] = novi;
pq.push({-novi, {-1, sus}});
}
}
for (auto sus : sus_bad[node]) {
llint novi = best[node] + 1;
int curr_ost = novi % d[sus];
if (bio[koji[sus]][curr_ost]) continue;
bio[koji[sus]][curr_ost] = 1;
for (int i = 0; i < d[sus]; i++) {
curr_ost = novi % d[sus];
if (curr_ost != ost[sus] && novi < dist[koji[sus]][curr_ost]) {
dist[koji[sus]][curr_ost] = novi;
pq.push({-novi, {koji[sus], curr_ost}});
}
novi++;
}
}
} else {
if (best[node] == INF) {
best[node] = pq_dist;
for (auto sus : sus_good[node]) {
llint novi = best[node] + 1;
if (novi < best[sus]) {
best[sus] = novi;
pq.push({-novi, {-1, sus}});
}
}
}
for (auto sus : sus_bad[node]) {
if (sus == special[node]) continue;
llint novi = best[node] + 1;
for (int i = 0; i < d[sus]; i++) {
int curr_ost = novi % d[sus];
if (curr_ost != ost[sus] && novi < dist[koji[sus]][curr_ost]) {
dist[koji[sus]][curr_ost] = novi;
pq.push({-novi, {koji[sus], curr_ost}});
}
novi += d[node];
}
}
int sus = special[node];
llint novi = best[node] + 1;
int curr_ost = novi % d[node];
if (curr_ost != ost[node] && curr_ost != ost[sus] && novi < dist[koji[sus]][curr_ost]) {
dist[koji[sus]][curr_ost] = novi;
pq.push({-novi, {koji[sus], curr_ost}});
}
}
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
edges.push_back({a, b});
}
cin >> k;
for (int i = 1; i <= k; i++) {
int len;
cin >> len;
vector <int> tmp;
for (int j = 0; j < len; j++) {
int node;
cin >> node;
tmp.push_back(node);
watched[node] = 1;
d[node] = len;
ost[node] = j;
}
for (int i = 1; i < tmp.size(); i++) {
special[tmp[i]] = tmp[i - 1];
}
special[tmp[0]] = tmp.back();
}
build();
dijkstra();
if (best[n] == INF) cout << "impossible"; else cout << best[n];
return 0;
}
Compilation message
watchmen.cpp: In function 'void build()':
watchmen.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 0; i < bad.size(); i++) {
| ~~^~~~~~~~~~~~
watchmen.cpp: In function 'void dijkstra()':
watchmen.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < bad.size(); i++) {
| ~~^~~~~~~~~~~~
watchmen.cpp: In function 'int main()':
watchmen.cpp:160:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for (int i = 1; i < tmp.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1550 ms |
15976 KB |
Output is correct |
| 2 |
Incorrect |
77 ms |
20164 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1547 ms |
15984 KB |
Output is correct |
| 2 |
Incorrect |
74 ms |
20132 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1547 ms |
15984 KB |
Output is correct |
| 2 |
Incorrect |
74 ms |
20132 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1547 ms |
15984 KB |
Output is correct |
| 2 |
Incorrect |
74 ms |
20132 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1550 ms |
15976 KB |
Output is correct |
| 2 |
Incorrect |
77 ms |
20164 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1550 ms |
15976 KB |
Output is correct |
| 2 |
Incorrect |
77 ms |
20164 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1550 ms |
15976 KB |
Output is correct |
| 2 |
Incorrect |
77 ms |
20164 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
