// 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];
const int D = 3000;
vector<int> q[D];
int maxd = 0;
int curd = 0;
void relax(int id, int d) {
if (!(d - curd < D)) {
cout << " : " << d - curd << ", too big" << "\n";
exit(0);
}
if (d < dp[id]) {
dp[id] = d;
q[d % D].push_back(id);
maxd = max(maxd, d);
}
}
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;
}
relax(single_vertex_id[1], 0);
for (int cd = 0; cd <= maxd; cd++) {
curd = cd;
while (!q[cd % D].empty()) {
int idv = q[cd % D].back(), d = cd;
q[cd % D].pop_back();
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--;
int vertex = all[p].first, vecin = all[p].second;
int l = cycles[cycle_id[vertex]].size();
int l_vecin = cycles[cycle_id[vecin]].size();
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;
}
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
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;
}
}
}
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:64:5: error: 'freopen_s' was not declared in this scope; did you mean 'freopen64'?
64 | freopen_s(&stream, "input.txt", "r", stdin);
| ^~~~~~~~~
| freopen64
watchmen.cpp:145:9: warning: unused variable 'vertex' [-Wunused-variable]
145 | int vertex = it.first.first, vecin = it.first.second;
| ^~~~~~
