Submission #572054

#	Time	Username	Problem	Language	Result	Execution time	Memory
572054		jjang36524	From Hacks to Snitches (BOI21_watchmen)	C++14	100 / 100	2892 ms	140976 KiB

watchmen

#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()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	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 (t!=dp[curp][curr])
		{
			continue;
		}
		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 = jw+(curr+cylen[pa]-cypos[curp])%cylen[pa];
					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[nexp] + 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:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (i = 0; i < link[curp].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:90:78: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   90 |    if (pa && pb && (pa != pb || (cypos[curp] + 1) % cylen[pa] != cypos[nexp] && (cypos[nexp] + 1) % cylen[pb] != cypos[curp]))
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 25 / 25
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20