oj.uz

Submission #771802

# Submission time Handle Problem Language Result Execution time Memory
771802 2023-07-03T09:35:50 Z LittleCube From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 475892 KB 
#include <bits/stdc++.h>
#define ll long long
#define state tuple<int, int, int>
#define F first
#define S second
using namespace std;

int N, M, K, L, l[2500005], r[2500005], nxt[2500005], mp[2000];
ll cnt = 0;
vector<int> v[2000];
vector<ll> dis[2500005];
vector<bitset<128>> vis[2500005];
vector<int> E[2500005];
vector<state> pq[1000005];

bool good(int u, ll t)
{
	return l[u] == 1 || t % l[u] != r[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);
	}
	for (int i = 1; i <= N; i++)
		l[i] = 1;
	cin >> K;
	for (int i = 1; i <= K; i++)
	{
		int k;
		cin >> k;
		if (mp[k] == 0)
			mp[k] = ++L;
		v[i].resize(k);
		for (int j = 0; j < k; j++)
		{
			cin >> v[i][j];
			l[v[i][j]] = k;
			r[v[i][j]] = j;
			vis[v[i][j]].resize(k);
		}
		for (int j = 0; j < k; j++)
			nxt[v[i][j]] = v[i][(j + 1) % k];
	}
	assert(L < 128);
	for (int i = 1; i <= N; i++)
		dis[i].resize(l[i], (ll)1e18);
	dis[1][0] = 0;

	pq[0].emplace_back(state{1, 0, 0});

	auto cycle = [&](int d, int u, int b)
	{
		cnt++;
		// u -> b
		int rem = (d + 1) % l[b];
		if (vis[b][rem][mp[l[u]]])
			return;
		if (goodmove(u, b, d + 1))
			if (dis[b][rem] > d + 1)
			{
				dis[b][rem] = d + 1;
				pq[d + 1].emplace_back(state{b, rem, 0});
			}

		vis[b][rem][mp[l[u]]] = 1;

		if (d + l[u] <= 4 * N)
			pq[d + l[u]].emplace_back(state{u, 0, b});
	};

	auto normal = [&](int d, int u, int k)
	{
		for (auto v : E[u])
			if (l[v] == 1 && d + 1 < dis[v][0])
			{
				dis[v][0] = d + 1;
				pq[d + 1].emplace_back(state{v, 0, 0});
			}
			else if (l[v] > 1)
			{
				if (!goodmove(u, v, d + 1) && l[u] % l[v] == 0)
					continue;
				cycle(d, u, v);
			}

		int rem = (d + 1) % l[u];
		if (good(u, d + 1) && dis[u][rem] > d + 1)
		{
			dis[u][rem] = d + 1;
			pq[d + 1].emplace_back(state{u, rem, 0});
		}
	};

	for (int d = 0; d <= 4 * N; d++)
		for (auto [u, k, b] : pq[d])
		{
			if (!b && d > dis[u][k])
				continue;
			if (!b)
				normal(d, u, k);
			else
				cycle(d, u, b);
		}
	// for (int i = 1; i <= N; i++)
	// {
	// 	cout << i << ":";
	// 	for (auto j : dis[i])
	// 		cout << ' ' << j;
	// 	cout << '\n';
	// }
	assert(cnt <= 2 * 25 * 350 * 200);
	cerr << "update counter " << cnt << '\n';
	if (dis[N][0] >= 1e18)
		cout << "impossible\n";
	else
	{
		assert(dis[N][0] <= N * 5);
		cout << dis[N][0] << '\n';
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 201780 KB Output is correct
2 Correct 139 ms 211060 KB Output is correct
3 Correct 129 ms 211076 KB Output is correct
4 Correct 165 ms 210844 KB Output is correct
5 Correct 88 ms 200652 KB Output is correct
6 Correct 158 ms 210748 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 201720 KB Output is correct
2 Correct 138 ms 211112 KB Output is correct
3 Correct 145 ms 211028 KB Output is correct
4 Correct 156 ms 210796 KB Output is correct
5 Correct 90 ms 200788 KB Output is correct
6 Correct 134 ms 210748 KB Output is correct
7 Correct 130 ms 210488 KB Output is correct
8 Correct 144 ms 210576 KB Output is correct
9 Correct 126 ms 210496 KB Output is correct
10 Correct 136 ms 209980 KB Output is correct
11 Correct 128 ms 209224 KB Output is correct
12 Correct 127 ms 210380 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 201720 KB Output is correct
2 Correct 138 ms 211112 KB Output is correct
3 Correct 145 ms 211028 KB Output is correct
4 Correct 156 ms 210796 KB Output is correct
5 Correct 90 ms 200788 KB Output is correct
6 Correct 134 ms 210748 KB Output is correct
7 Correct 130 ms 210488 KB Output is correct
8 Correct 144 ms 210576 KB Output is correct
9 Correct 126 ms 210496 KB Output is correct
10 Correct 136 ms 209980 KB Output is correct
11 Correct 128 ms 209224 KB Output is correct
12 Correct 127 ms 210380 KB Output is correct
13 Correct 137 ms 202392 KB Output is correct
14 Correct 143 ms 212180 KB Output is correct
15 Correct 139 ms 211096 KB Output is correct
16 Correct 156 ms 210764 KB Output is correct
17 Correct 90 ms 200656 KB Output is correct
18 Correct 130 ms 210800 KB Output is correct
19 Correct 128 ms 210564 KB Output is correct
20 Correct 133 ms 210628 KB Output is correct
21 Correct 128 ms 210600 KB Output is correct
22 Correct 139 ms 209988 KB Output is correct
23 Correct 125 ms 209224 KB Output is correct
24 Correct 131 ms 210340 KB Output is correct
25 Correct 1182 ms 257960 KB Output is correct
26 Correct 985 ms 264252 KB Output is correct
27 Correct 999 ms 259748 KB Output is correct
28 Correct 872 ms 262304 KB Output is correct
29 Execution timed out 6018 ms 247212 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 201720 KB Output is correct
2 Correct 138 ms 211112 KB Output is correct
3 Correct 145 ms 211028 KB Output is correct
4 Correct 156 ms 210796 KB Output is correct
5 Correct 90 ms 200788 KB Output is correct
6 Correct 134 ms 210748 KB Output is correct
7 Correct 130 ms 210488 KB Output is correct
8 Correct 144 ms 210576 KB Output is correct
9 Correct 126 ms 210496 KB Output is correct
10 Correct 136 ms 209980 KB Output is correct
11 Correct 128 ms 209224 KB Output is correct
12 Correct 127 ms 210380 KB Output is correct
13 Correct 137 ms 202392 KB Output is correct
14 Correct 143 ms 212180 KB Output is correct
15 Correct 139 ms 211096 KB Output is correct
16 Correct 156 ms 210764 KB Output is correct
17 Correct 90 ms 200656 KB Output is correct
18 Correct 130 ms 210800 KB Output is correct
19 Correct 128 ms 210564 KB Output is correct
20 Correct 133 ms 210628 KB Output is correct
21 Correct 128 ms 210600 KB Output is correct
22 Correct 139 ms 209988 KB Output is correct
23 Correct 125 ms 209224 KB Output is correct
24 Correct 131 ms 210340 KB Output is correct
25 Correct 1182 ms 257960 KB Output is correct
26 Correct 985 ms 264252 KB Output is correct
27 Correct 999 ms 259748 KB Output is correct
28 Correct 872 ms 262304 KB Output is correct
29 Execution timed out 6018 ms 247212 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 201780 KB Output is correct
2 Correct 139 ms 211060 KB Output is correct
3 Correct 129 ms 211076 KB Output is correct
4 Correct 165 ms 210844 KB Output is correct
5 Correct 88 ms 200652 KB Output is correct
6 Correct 158 ms 210748 KB Output is correct
7 Correct 137 ms 201720 KB Output is correct
8 Correct 138 ms 211112 KB Output is correct
9 Correct 145 ms 211028 KB Output is correct
10 Correct 156 ms 210796 KB Output is correct
11 Correct 90 ms 200788 KB Output is correct
12 Correct 134 ms 210748 KB Output is correct
13 Correct 130 ms 210488 KB Output is correct
14 Correct 144 ms 210576 KB Output is correct
15 Correct 126 ms 210496 KB Output is correct
16 Correct 136 ms 209980 KB Output is correct
17 Correct 128 ms 209224 KB Output is correct
18 Correct 127 ms 210380 KB Output is correct
19 Correct 89 ms 199960 KB Output is correct
20 Correct 89 ms 199956 KB Output is correct
21 Correct 88 ms 199940 KB Output is correct
22 Correct 142 ms 202396 KB Output is correct
23 Correct 139 ms 212160 KB Output is correct
24 Correct 137 ms 210996 KB Output is correct
25 Correct 173 ms 210812 KB Output is correct
26 Correct 91 ms 200704 KB Output is correct
27 Correct 136 ms 210796 KB Output is correct
28 Correct 129 ms 210508 KB Output is correct
29 Correct 131 ms 210676 KB Output is correct
30 Correct 127 ms 210472 KB Output is correct
31 Correct 155 ms 209900 KB Output is correct
32 Correct 133 ms 209188 KB Output is correct
33 Correct 127 ms 210380 KB Output is correct
34 Correct 1147 ms 254300 KB Output is correct
35 Correct 1328 ms 249092 KB Output is correct
36 Correct 1219 ms 251172 KB Output is correct
37 Correct 1006 ms 256980 KB Output is correct
38 Correct 1104 ms 255692 KB Output is correct
39 Execution timed out 6056 ms 475892 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 201780 KB Output is correct
2 Correct 139 ms 211060 KB Output is correct
3 Correct 129 ms 211076 KB Output is correct
4 Correct 165 ms 210844 KB Output is correct
5 Correct 88 ms 200652 KB Output is correct
6 Correct 158 ms 210748 KB Output is correct
7 Correct 137 ms 201720 KB Output is correct
8 Correct 138 ms 211112 KB Output is correct
9 Correct 145 ms 211028 KB Output is correct
10 Correct 156 ms 210796 KB Output is correct
11 Correct 90 ms 200788 KB Output is correct
12 Correct 134 ms 210748 KB Output is correct
13 Correct 130 ms 210488 KB Output is correct
14 Correct 144 ms 210576 KB Output is correct
15 Correct 126 ms 210496 KB Output is correct
16 Correct 136 ms 209980 KB Output is correct
17 Correct 128 ms 209224 KB Output is correct
18 Correct 127 ms 210380 KB Output is correct
19 Correct 137 ms 202392 KB Output is correct
20 Correct 143 ms 212180 KB Output is correct
21 Correct 139 ms 211096 KB Output is correct
22 Correct 156 ms 210764 KB Output is correct
23 Correct 90 ms 200656 KB Output is correct
24 Correct 130 ms 210800 KB Output is correct
25 Correct 128 ms 210564 KB Output is correct
26 Correct 133 ms 210628 KB Output is correct
27 Correct 128 ms 210600 KB Output is correct
28 Correct 139 ms 209988 KB Output is correct
29 Correct 125 ms 209224 KB Output is correct
30 Correct 131 ms 210340 KB Output is correct
31 Correct 1182 ms 257960 KB Output is correct
32 Correct 985 ms 264252 KB Output is correct
33 Correct 999 ms 259748 KB Output is correct
34 Correct 872 ms 262304 KB Output is correct
35 Execution timed out 6018 ms 247212 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 201780 KB Output is correct
2 Correct 139 ms 211060 KB Output is correct
3 Correct 129 ms 211076 KB Output is correct
4 Correct 165 ms 210844 KB Output is correct
5 Correct 88 ms 200652 KB Output is correct
6 Correct 158 ms 210748 KB Output is correct
7 Correct 137 ms 201720 KB Output is correct
8 Correct 138 ms 211112 KB Output is correct
9 Correct 145 ms 211028 KB Output is correct
10 Correct 156 ms 210796 KB Output is correct
11 Correct 90 ms 200788 KB Output is correct
12 Correct 134 ms 210748 KB Output is correct
13 Correct 130 ms 210488 KB Output is correct
14 Correct 144 ms 210576 KB Output is correct
15 Correct 126 ms 210496 KB Output is correct
16 Correct 136 ms 209980 KB Output is correct
17 Correct 128 ms 209224 KB Output is correct
18 Correct 127 ms 210380 KB Output is correct
19 Correct 137 ms 202392 KB Output is correct
20 Correct 143 ms 212180 KB Output is correct
21 Correct 139 ms 211096 KB Output is correct
22 Correct 156 ms 210764 KB Output is correct
23 Correct 90 ms 200656 KB Output is correct
24 Correct 130 ms 210800 KB Output is correct
25 Correct 128 ms 210564 KB Output is correct
26 Correct 133 ms 210628 KB Output is correct
27 Correct 128 ms 210600 KB Output is correct
28 Correct 139 ms 209988 KB Output is correct
29 Correct 125 ms 209224 KB Output is correct
30 Correct 131 ms 210340 KB Output is correct
31 Correct 1182 ms 257960 KB Output is correct
32 Correct 985 ms 264252 KB Output is correct
33 Correct 999 ms 259748 KB Output is correct
34 Correct 872 ms 262304 KB Output is correct
35 Execution timed out 6018 ms 247212 KB Time limit exceeded
36 Halted 0 ms 0 KB -