#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define rep(i, n) for(int i = 0; i<(int)n; ++i)
const int mxN = 1e5+5, M = 1e9+7;
vector<ll> d[mxN];
vector<int> adj[mxN];
int n, m;
struct node{
int x, y; ll dist;
bool operator <(const node &n)const{
return dist > n.dist;
}
};
void solve(int n, vector<pair<int, int>> edg, vector<int> v, int s, int t){
for(auto &[a, b] : edg){
adj[a].push_back(b);
adj[b].push_back(a);
}
rep(i, n) sort(adj[i].begin(), adj[i].end());
int p = 0;
vector<pair<int, int>> cycles;
for(int i = 0; i<v.size(); ++i){
for(int j = 0; j<v[i]; ++j){
d[p++].resize(v[i], 1e18);
cycles.emplace_back(i, j);
}
}
while(p<n){
d[p++].resize(1, 1e18);
cycles.emplace_back(-1, 0);
}
priority_queue<node> pq;
auto enq = [&](int v, ll dist){
if(d[v].size() > 1 && dist%d[v].size() == cycles[v].second) return;
if(d[v][dist%d[v].size()] > dist){
d[v][dist%d[v].size()] = dist;
pq.push({v, (int)(dist%d[v].size()), dist});
}
};
enq(s, 0);
vector<int> viscnt(n);
while(pq.size()){
auto x = pq.top();
pq.pop();
int v = x.x;
int w = x.y;
if(d[v][w] != x.dist) continue;
enq(v, x.dist+1);
viscnt[v]++;
if(d[v].size() == 1){
for(auto &y : adj[v]){
if(cycles[v].first >= 0 && cycles[v].first == cycles[y].first && w == cycles[y].second && (w+1)%d[v].size() == cycles[v].second){
continue;
}
enq(y, x.dist+1);
enq(y, x.dist+1 + ((cycles[y].second-x.dist)%d[y].size()+d[y].size()) % d[y].size());
}
}else{
vector<int> newlist;
for(auto &y : adj[v]){
if(cycles[v].first >= 0 && cycles[v].first == cycles[y].first && (w+1)%d[v].size() == cycles[v].second){
newlist.push_back(y);
continue;
}
auto promotionate = [&](ll x, ll cyc, ll xz){
ll ff = (x/cyc) * cyc + m;
if(ff < x) ff += cyc;
return ff;
};
if(d[y].size() == 1){
enq(y, x.dist+1);
}else if(cycles[v].first != cycles[y].first){
enq(y, x.dist+1);
ll val = promotionate(x.dist+1, d[y].size(), cycles[y].second);
if(val%d[v].size() != cycles[v].second){
enq(y, val+1);
}else{
newlist.push_back(y);
ll newdist = promotionate(val, d[v].size(), w);
enq(y, newdist+1);
ll ff = promotionate(newdist+1, d[y].size(), cycles[y].second);
if(ff%d[v].size() != cycles[v].second) enq(y, ff+1);
}
}else{
enq(y, x.dist+1);
if(cycles[y].second == (cycles[v].second+1)%d[v].size() || cycles[v].second == (cycles[y].second +1)%d[v].size()){
newlist.push_back(y);
}else{
ll ff = promotionate(x.dist+1, d[y].size(), cycles[y].second);
enq(y, ff+1);
}
}
}
adj[v] = newlist;
}
}
ll ans = *min_element(d[t].begin(), d[t].end());
if(ans >= 1e16) cout << "impossible\n";
else cout << ans << "\n";
}
int main(){
#ifdef _DEBUG
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
cin >> n >> m;
vector<pair<int, int>> edg;
rep(i, m){
int a, b;
cin >> a >> b, --a, --b;
edg.emplace_back(a, b);
}
vector<int> idx(n, -1);
int cnt = 0;
int k;
cin >> k;
vector<int> ff(k);
rep(i, k){
cin >> ff[i];
rep(j, ff[i]){
int x;
cin >> x, --x;
idx[x] = cnt++;
}
}
rep(i, n){
if(idx[i] == -1) idx[i] = cnt++;
}
for(int i = 0; i<m; ++i){
edg[i] = {idx[edg[i].first], idx[edg[i].second]};
}
solve(n, edg, ff, idx[0], idx[n-1]);
}
Compilation message
watchmen.cpp: In function 'void solve(int, std::vector<std::pair<int, int> >, std::vector<int>, int, int)':
watchmen.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i = 0; i<v.size(); ++i){
| ~^~~~~~~~~
watchmen.cpp: In lambda function:
watchmen.cpp:41:48: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
41 | if(d[v].size() > 1 && dist%d[v].size() == cycles[v].second) return;
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp: In function 'void solve(int, std::vector<std::pair<int, int> >, std::vector<int>, int, int)':
watchmen.cpp:59:125: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
59 | if(cycles[v].first >= 0 && cycles[v].first == cycles[y].first && w == cycles[y].second && (w+1)%d[v].size() == cycles[v].second){
| ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:68:100: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
68 | if(cycles[v].first >= 0 && cycles[v].first == cycles[y].first && (w+1)%d[v].size() == cycles[v].second){
| ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:83:40: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
83 | if(val%d[v].size() != cycles[v].second){
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:90:43: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
90 | if(ff%d[v].size() != cycles[v].second) enq(y, ff+1);
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:94:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | if(cycles[y].second == (cycles[v].second+1)%d[v].size() || cycles[v].second == (cycles[y].second +1)%d[v].size()){
watchmen.cpp:94:97: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | if(cycles[y].second == (cycles[v].second+1)%d[v].size() || cycles[v].second == (cycles[y].second +1)%d[v].size()){
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
7868 KB |
Output is correct |
| 2 |
Incorrect |
79 ms |
15684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
7888 KB |
Output is correct |
| 2 |
Incorrect |
49 ms |
15656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
7888 KB |
Output is correct |
| 2 |
Incorrect |
49 ms |
15656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
7888 KB |
Output is correct |
| 2 |
Incorrect |
49 ms |
15656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
7868 KB |
Output is correct |
| 2 |
Incorrect |
79 ms |
15684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
7868 KB |
Output is correct |
| 2 |
Incorrect |
79 ms |
15684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
7868 KB |
Output is correct |
| 2 |
Incorrect |
79 ms |
15684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
