oj.uz

Submission #771751

# Submission time Handle Problem Language Result Execution time Memory
771751 2023-07-03T08:51:13 Z LittleCube From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 249 ms 365788 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#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);
}

ll add(ll a, ll m)
{
	return a + 1 >= m ? a + 1 - m : a + 1;
}

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 = add(d, 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 = add(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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 249 ms 365788 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 238 ms 365728 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 238 ms 365728 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 238 ms 365728 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 249 ms 365788 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 249 ms 365788 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 249 ms 365788 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -