This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define INF 998244353
int cylen[1000];
int cycno[300100];
int cypos[300100];
vector<int>link[300100];
vector<int>dp[300100];
vector<bool>vis[300100];
priority_queue<pair<int, pair<int, int>>>x;
void upd(pair<int, int> pos)
{
int o = pos.second % cylen[cycno[pos.first]];
if ((cylen[cycno[pos.first]] == 1 || o != cypos[pos.first]) && pos.second < dp[pos.first][o])
{
dp[pos.first][o] = pos.second;
x.push({ {-pos.second},{pos.first,o} });
}
}
int getne(int cur, int nem, int mb)
{
return cur + (nem + mb - cur % mb) % mb;
}
int main()
{
int N, M, K;
cin >> N >> M;
int i;
for (i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
link[a].push_back(b);
link[b].push_back(a);
}
cin >> K;
cylen[0] = 1;
for (i = 1; i <= K; i++)
{
cin >> cylen[i];
int j;
for (j = 0; j < cylen[i]; j++)
{
int a;
cin >> a;
cycno[a] = i;
cypos[a] = j;
}
}
for (i = 1; i <= N; i++)
{
if (!cycno[i])
{
dp[i].resize(1, INF);
}
else
{
dp[i].resize(cylen[cycno[i]], INF);
}
vis[i].resize(dp[i].size());
}
upd({ 1,0 });
while (x.size())
{
auto cu = x.top();
x.pop();
int t = -cu.first;
int curp = cu.second.first;
int curr = cu.second.second;
if (vis[curp][curr])
{
continue;
}
vis[curp][curr] = 1;
for (i = 0; i < link[curp].size(); i++)
{
int nexp = link[curp][i];
int pa = cycno[curp];
int pb = cycno[nexp];
if (!pa || pa != pb || (cypos[nexp] + 1) % cylen[pa] != cypos[curp] || cypos[nexp] != curr)
{
upd({ nexp,t + 1 });
}
if (!pa && pb)
{
upd({ nexp,t + 1 + (cypos[nexp] + cylen[pb] - t % cylen[pb]) % cylen[pb] });
}
int re = 0;
if (pa && pb && (pa != pb || (cypos[curp] + 1) % cylen[pa] != cypos[nexp] && (cypos[nexp] + 1) % cylen[pb] != cypos[curp]))
{
int jw = getne(t, cypos[nexp], cylen[pb]);
int jjw = getne(jw, cypos[curp], cylen[pa]);
if (jw != jjw)
{
upd({ nexp,jw + 1 });
re = 1;
}
else
{
int bo = getne(cypos[curp], curr, cylen[pa]) -cypos[curp]+jw;
upd({ nexp,bo + 1 });
if (cylen[pb] % cylen[pa] && (cylen[pa] % cylen[pb] || (cypos[curp] + cylen[pa] - curr) % cylen[pa] >= cylen[pb]))
{
upd({ nexp,bo + 1 + (cypos[pb] + cylen[pb] - bo % cylen[pb] % cylen[pb]) });
}
}
}
if (!pa || !pb || re)
{
swap(link[curp][i], link[curp].back());
link[curp].pop_back();
i--;
}
}
upd({ curp, t + 1 });
}
if (dp[N][0] == 998244353)
{
cout << "impossible";
}
else
{
cout << dp[N][0];
}
}
Compilation message (stderr)
watchmen.cpp: In function 'int main()':
watchmen.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (i = 0; i < link[curp].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:89:78: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
89 | if (pa && pb && (pa != pb || (cypos[curp] + 1) % cylen[pa] != cypos[nexp] && (cypos[nexp] + 1) % cylen[pb] != cypos[curp]))
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |