#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
void debug(auto l, auto r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
using t3 = pair<ll,int>;
const int MAX_N = 300010, MAX_K = 2800, hol = 100;
const ll inf = 1ll << 55;
int n, m;
vector<int> edge[MAX_N], cyc[MAX_N];
ll dp[MAX_N][2];
int cid[MAX_N], csz[MAX_N], cpos[MAX_N];
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
// init everything
cin >> n >> m;
for (int a, b, i = 0;i < m;++i) {
cin >> a >> b;
edge[a].pb(b);
edge[b].pb(a);
}
for (int i = 1;i <= n;++i) {
dp[i][0] = dp[i][1] = inf;
csz[i] = 1;
}
int K;
cin >> K;
for (int i = 1;i <= K;++i) {
int len;
cin >> len;
cyc[i].resize(len);
int c = 0;
for (int &u : cyc[i]) {
cin >> u;
cid[u] = i;
csz[u] = len;
cpos[u] = c++;
}
}
//priority_queue<t3, vector<t3>, greater<t3>> q;
//queue<pair<ll,int>> q;
vector<vector<int>> q;
auto putin = [&](int d, int x) {
if (q.size() < d + 1) q.resize(d + 1);
q[d].pb(x);
};
// > d, when will x be hit
auto behit = [&](int x, ll d) {
ll a = d % csz[x], b = cpos[x];
if (a < b) return d + b - a;
return d + csz[x] - a + b;
};
auto upd = [&](int x, ll d) {
auto &A = dp[x][0], &B = dp[x][1];
bool ch = false;
if (d < A) {
putin(d, x);
swap(d, A);
ch = true;
}
if (d > behit(x, A) && d < B) {
if (!ch) putin(d, x);
swap(B, d);
}
};
upd(1, 0);
// when x's shortest path is d, I want to relax u
auto valid = [&](int x, ll d, int u) {
if (cid[u] == 0) return true;
if (d % csz[u] == cpos[u]) return false;
if (cid[x] == cid[u] && cpos[u] == (cpos[x] - 1 + csz[x]) % csz[u]) {
if (d % csz[u] == cpos[x]) return false;
}
return true;
};
auto relax = [&](int x, int u, ll d) {
if (cid[u] == 0) {
upd(u, d + 1);
return;
};
if (valid(x, d+1, u))
upd(u, d+1);
else if (valid(x, d+1, x) && valid(x, d+2, u))
upd(u, d+2);
ll xh = behit(x, d), uh = behit(u, d);
if (cid[x] == 0) xh = inf;
if (xh <= uh) return;
upd(u, uh + 1);
};
// shortest path
for (int d = 0;d < q.size();++d) {
for (int i = 0;i < q[d].size();++i) {
int x = q[d][i];
if (d != dp[x][0] && d != dp[x][1]) continue;
for (int u : edge[x])
relax(x, u, d);
}
}
// now there are no two cycle being connected
// check if at x, time is d can move to
ll res = inf;
for (auto v : dp[n]) chmin(res, v);
if (res == inf) cout << "impossible\n";
else cout << res << '\n';
}
Compilation message
watchmen.cpp: In lambda function:
watchmen.cpp:62:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
62 | if (q.size() < d + 1) q.resize(d + 1);
| ~~~~~~~~~^~~~~~~
watchmen.cpp: In function 'int32_t main()':
watchmen.cpp:115:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int d = 0;d < q.size();++d) {
| ~~^~~~~~~~~~
watchmen.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (int i = 0;i < q[d].size();++i) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
15332 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
25512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
15360 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
25528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
15360 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
25528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
15360 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
25528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
15332 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
25512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
15332 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
25512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
15332 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
25512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
