// pana la ora 1
bool home = 1;
bool verbose = 1;
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <cassert>
using namespace std;
struct T {
int v;
int r;
};
const int N = 250000 + 7;
const int V = (int)1e7 + 7;
const int INF = (int)1e9 + 7;
int n;
int m;
int cnt_cycles;
int suml;
vector<pair<int, int>> edges;
vector<int> cycles[N];
int cycle_id[N];
int cycle_location[N];
int single_vertex_id[N];
vector<int> cycle_vertex_id[N];
vector<int> splash_vertex_id[N];
int dp[V];
T what[V];
int y;
vector<int> g[N];
priority_queue<pair<int, int>> pq;
void relax(int id, int d) {
if (d < dp[id]) {
dp[id] = d;
pq.push({ -dp[id], id });
}
}
int main() {
if (!home) {
verbose = 0;
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
if (home) {
verbose = 1;
FILE* stream;
freopen_s(&stream, "input.txt", "r", stdin);
}
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
edges.push_back({ a, b });
}
cin >> cnt_cycles;
for (int i = 1; i <= cnt_cycles; i++) {
int l;
cin >> l;
suml += l;
cycles[i].resize(l);
for (int j = 0; j < (int)cycles[i].size(); j++) {
cin >> cycles[i][j];
cycle_id[cycles[i][j]] = i;
cycle_location[cycles[i][j]] = j;
}
if (verbose) {
cout << " ---> ";
for (auto& v : cycles[i]) {
cout << v << " ";
}
cout << "\n";
}
}
for (int a = 1; a <= n; a++) {
if (cycle_id[a] == 0) {
y++;
single_vertex_id[a] = y;
what[y] = { a, 0 };
}
else {
int id = cycle_id[a];
cycle_vertex_id[a].resize((int)cycles[id].size());
splash_vertex_id[a].resize((int)cycles[id].size());
for (int j = 0; j < (int)cycles[id].size(); j++) {
y++;
cycle_vertex_id[a][j] = y;
what[y] = { a, j };
}
for (int j = 0; j < (int)cycles[id].size(); j++) {
y++;
splash_vertex_id[a][j] = y;
what[y] = { a, -(j + 1) };
}
}
}
if (verbose) {
cout << "y = " << y << "\n";
cout << "################################################################################### \n";
}
map<pair<int, int>, int> spec;
vector<pair<int, int>> all;
for (int vertex = 1; vertex <= n; vertex++) {
if (int cycle = cycle_id[vertex]) {
for (auto& vecin : g[vertex]) {
if (int cycle_vecin = cycle_id[vecin]) {
// vecin is on a cycle
if (cycle_vecin != cycle) {
// vecin is on a different cycle
spec[{vertex, vecin}] = 0;
}
}
}
}
}
vector<vector<int>> ids;
for (auto& it : spec) {
it.second = (int)all.size();
all.push_back(it.first);
int vertex = it.first.first, vecin = it.first.second;
int l_vecin = cycles[cycle_id[vecin]].size();
ids.push_back({});
ids.back().resize(l_vecin);
for (int r = 0; r < l_vecin; r++) {
y++;
ids.back()[r] = y;
what[y] = { -(int)ids.size(), r };
}
}
for (int i = 1; i <= y; i++) {
dp[i] = INF;
}
dp[single_vertex_id[1]] = 0;
pq.push({ 0, single_vertex_id[1] });
while (!pq.empty()) {
int d = -pq.top().first;
int idv = pq.top().second;
pq.pop();
if (dp[idv] != d) {
continue;
}
int vertex = what[idv].v;
int r = what[idv].r;
if (vertex < 0) {
// cout << "aici\n";
int p = vertex;
p *= -1;
p--;
assert(0 <= p && p < (int)ids.size());
int vertex = all[p].first, vecin = all[p].second;
int l = cycles[cycle_id[vertex]].size();
int l_vecin = cycles[cycle_id[vecin]].size();
assert((int)ids[p].size() == l_vecin);
relax(ids[p][(d + l) % l_vecin], d + l);
if (d % l_vecin == cycle_location[vecin]) {
continue;
}
relax(cycle_vertex_id[vecin][d % l_vecin], d);
continue;
}
if (r < 0) {
r *= -1;
r--;
int cycle = cycle_id[vertex];
int l = cycles[cycle].size();
relax(splash_vertex_id[vertex][(d + 1) % l], d + 1);
if (d % l != cycle_location[vertex]) {
relax(cycle_vertex_id[vertex][d % l], d);
}
continue;
}
if (cycle_id[vertex] == 0) {
for (auto& vecin : g[vertex]) {
if (cycle_id[vecin] == 0) {
// vecin is a single vertex
relax(single_vertex_id[vecin], d + 1);
}
else {
// vecin is on a cycle
int cycle_vecin = cycle_id[vecin];
int l_vecin = cycles[cycle_vecin].size();
relax(splash_vertex_id[vecin][(d + 1) % l_vecin], d + 1);
continue;
for (int twait = 0; twait < l_vecin; twait++) {
// la momentul d + 1 + twait
if ((d + 1 + twait) % l_vecin == cycle_location[vecin]) {
continue;
}
relax(cycle_vertex_id[vecin][(d + 1 + twait) % l_vecin], d + 1 + twait);
}
}
}
continue;
}
if (cycle_id[vertex] != 0) {
int cycle = cycle_id[vertex];
int l = cycles[cycle].size();
/*
wait a moment here
*/
if ((d + 1) % l != cycle_location[vertex]) {
relax(cycle_vertex_id[vertex][(d + 1) % l], d + 1);
}
/*
don't wait a moment here
*/
for (auto& vecin : g[vertex]) {
if (cycle_id[vecin] == 0) {
// vecin is a single vertex
relax(single_vertex_id[vecin], d + 1);
}
else {
// vecin is on a cycle
int cycle_vecin = cycle_id[vecin];
int l_vecin = cycles[cycle_vecin].size();
if (cycle_vecin == cycle) {
// vecin is on the same cycle
if ((d + 1) % l_vecin == cycle_location[vecin]) {
continue;
}
if (d % l_vecin == cycle_location[vecin] && (d + 1) % l_vecin == cycle_location[vertex]) {
continue;
}
relax(cycle_vertex_id[vecin][(d + 1) % l_vecin], d + 1);
/*
vertex -> vecin <- vecin2
*/
}
else {
// vecin is on a different cycle
assert(spec.count({ vertex, vecin }));
int p = spec[{vertex, vecin}];
// cout << "gest:" << (int)pq.size()<<" "<< ids[p][(d + 1) % l_vecin]<< " vs "<<1<<"..."<<y << "\n";
relax(ids[p][(d + 1) % l_vecin], d + 1);
continue;
for (int j = 0; j <= l_vecin; j++) {
int twait = j * l;
// la momentul d + 1 + twait
if ((d + 1 + twait) % l_vecin == cycle_location[vecin]) {
continue;
}
relax(cycle_vertex_id[vecin][(d + 1 + twait) % l_vecin], d + 1 + twait);
}
}
}
}
continue;
}
}
int sol = dp[single_vertex_id[n]];
if (sol == INF) {
cout << "impossible\n";
return 0;
}
cout << sol << "\n";
return 0;
}
Compilation message
watchmen.cpp: In function 'int main()':
watchmen.cpp:57:5: error: 'freopen_s' was not declared in this scope; did you mean 'freopen64'?
57 | freopen_s(&stream, "input.txt", "r", stdin);
| ^~~~~~~~~
| freopen64
watchmen.cpp:138:9: warning: unused variable 'vertex' [-Wunused-variable]
138 | int vertex = it.first.first, vecin = it.first.second;
| ^~~~~~
