Submission #771746

#	Time	Username	Problem	Language	Result	Execution time	Memory
771746		LittleCube	From Hacks to Snitches (BOI21_watchmen)	C++17	40 / 100	6073 ms	281408 KiB

watchmen

#include <bits/stdc++.h>
#define ll long long
#define state tuple<ll, int, int, int>
#define F first
#define S second
using namespace std;

int N, M, K, L, l[2500005], r[2500005], nxt[2500005];
vector<int> v[2000];
vector<ll> dis[2500005];
vector<bitset<1501>> vis[2500005];
vector<int> E[2500005];

bool good(int u, ll t)
{
	return r[u] == 0 || v[r[u]][t % l[r[u]]] != u;
}

bool goodmove(int u, int v, ll t)
{
	if (u == nxt[v])
		return good(u, t) && good(v, t);
	else
		return good(v, t);
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; i++)
	{
		int u, v;
		cin >> u >> v;
		E[u].emplace_back(v);
		E[v].emplace_back(u);
	}
	l[0] = 1;
	cin >> K;
	for (int i = 1; i <= K; i++)
	{
		cin >> l[i];
		L = max(L, l[i]);
		v[i].resize(l[i]);
		for (int j = 0; j < l[i]; j++)
		{
			cin >> v[i][j];
			r[v[i][j]] = i;
			vis[v[i][j]].resize(l[i]);
		}
		for (int j = 0; j < l[i]; j++)
			nxt[v[i][j]] = v[i][(j + 1) % l[i]];
	}
	for (int i = 1; i <= N; i++)
		dis[i].resize(l[r[i]], (ll)1e18);
	dis[1][0] = 0;
	priority_queue<state, vector<state>, greater<state>> pq;
	pq.push(state{0, 1, 0, 0});
	while (!pq.empty())
	{
		auto [d, u, k, b] = pq.top();
		pq.pop();
		if (!b && d > dis[u][k])
			continue;
		if (!b)
		{
			for (auto v : E[u])
				if (r[v] == 0 && d + 1 < dis[v][0])
				{
					dis[v][0] = d + 1;
					pq.push(state{d + 1, v, 0, 0});
				}
				else if (r[v])
				{
					if (!goodmove(u, v, d + 1) && l[r[u]] % l[r[v]] == 0)
						continue;
					pq.push(state{d, u, k, v});
				}

			int rem = (d + 1) % l[r[u]];
			if (good(u, d + 1) && dis[u][rem] > d + 1)
			{
				dis[u][rem] = d + 1;
				pq.push(state{d + 1, u, rem, 0});
			}
		}
		else
		{
			// u -> b
			int rem = (d + 1) % l[r[b]];
			if (vis[b][rem][l[r[u]]])
				continue;
			if (goodmove(u, b, d + 1))
			{
				vis[b][rem][l[r[u]]] = 1;
				if (dis[b][rem] > d + 1)
				{
					dis[b][rem] = d + 1;
					pq.push(state{d + 1, b, rem, 0});
				}
			}
			pq.push(state{d + l[r[u]], u, k, b});
		}
	}
	// for (int i = 1; i <= N; i++)
	// {
	// 	cout << i << ":";
	// 	for (auto j : dis[i])
	// 		cout << ' ' << j;
	// 	cout << '\n';
	// }
	if (dis[N][0] >= 1e18)
		cout << "impossible\n";
	else
		cout << dis[N][0] << '\n';
}

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