oj.uz

Submission #771810

# Submission time Handle Problem Language Result Execution time Memory
771810 2023-07-03T09:39:47 Z LittleCube From Hacks to Snitches (BOI21_watchmen) C++17
40 / 100
 5643 ms 499724 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[1000006];

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 < 80);
	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
		assert(cnt <= 2 * 350 * 350 * max(20, L));
		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';
	// }
	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 136 ms 201692 KB Output is correct
2 Correct 176 ms 211120 KB Output is correct
3 Correct 160 ms 209972 KB Output is correct
4 Correct 171 ms 209732 KB Output is correct
5 Correct 90 ms 200724 KB Output is correct
6 Correct 130 ms 209676 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 201740 KB Output is correct
2 Correct 149 ms 211120 KB Output is correct
3 Correct 130 ms 209868 KB Output is correct
4 Correct 164 ms 209636 KB Output is correct
5 Correct 87 ms 200656 KB Output is correct
6 Correct 146 ms 209612 KB Output is correct
7 Correct 158 ms 209348 KB Output is correct
8 Correct 126 ms 209484 KB Output is correct
9 Correct 126 ms 209356 KB Output is correct
10 Correct 137 ms 208756 KB Output is correct
11 Correct 141 ms 207980 KB Output is correct
12 Correct 126 ms 209120 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 201740 KB Output is correct
2 Correct 149 ms 211120 KB Output is correct
3 Correct 130 ms 209868 KB Output is correct
4 Correct 164 ms 209636 KB Output is correct
5 Correct 87 ms 200656 KB Output is correct
6 Correct 146 ms 209612 KB Output is correct
7 Correct 158 ms 209348 KB Output is correct
8 Correct 126 ms 209484 KB Output is correct
9 Correct 126 ms 209356 KB Output is correct
10 Correct 137 ms 208756 KB Output is correct
11 Correct 141 ms 207980 KB Output is correct
12 Correct 126 ms 209120 KB Output is correct
13 Correct 138 ms 201740 KB Output is correct
14 Correct 142 ms 211120 KB Output is correct
15 Correct 139 ms 209972 KB Output is correct
16 Correct 160 ms 209708 KB Output is correct
17 Correct 89 ms 200708 KB Output is correct
18 Correct 131 ms 209656 KB Output is correct
19 Correct 126 ms 209376 KB Output is correct
20 Correct 128 ms 209464 KB Output is correct
21 Correct 130 ms 209452 KB Output is correct
22 Correct 144 ms 208812 KB Output is correct
23 Correct 132 ms 207964 KB Output is correct
24 Correct 128 ms 209140 KB Output is correct
25 Correct 1110 ms 257588 KB Output is correct
26 Correct 1055 ms 264072 KB Output is correct
27 Correct 984 ms 259528 KB Output is correct
28 Correct 844 ms 262012 KB Output is correct
29 Runtime error 3947 ms 499724 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 201740 KB Output is correct
2 Correct 149 ms 211120 KB Output is correct
3 Correct 130 ms 209868 KB Output is correct
4 Correct 164 ms 209636 KB Output is correct
5 Correct 87 ms 200656 KB Output is correct
6 Correct 146 ms 209612 KB Output is correct
7 Correct 158 ms 209348 KB Output is correct
8 Correct 126 ms 209484 KB Output is correct
9 Correct 126 ms 209356 KB Output is correct
10 Correct 137 ms 208756 KB Output is correct
11 Correct 141 ms 207980 KB Output is correct
12 Correct 126 ms 209120 KB Output is correct
13 Correct 138 ms 201740 KB Output is correct
14 Correct 142 ms 211120 KB Output is correct
15 Correct 139 ms 209972 KB Output is correct
16 Correct 160 ms 209708 KB Output is correct
17 Correct 89 ms 200708 KB Output is correct
18 Correct 131 ms 209656 KB Output is correct
19 Correct 126 ms 209376 KB Output is correct
20 Correct 128 ms 209464 KB Output is correct
21 Correct 130 ms 209452 KB Output is correct
22 Correct 144 ms 208812 KB Output is correct
23 Correct 132 ms 207964 KB Output is correct
24 Correct 128 ms 209140 KB Output is correct
25 Correct 1110 ms 257588 KB Output is correct
26 Correct 1055 ms 264072 KB Output is correct
27 Correct 984 ms 259528 KB Output is correct
28 Correct 844 ms 262012 KB Output is correct
29 Runtime error 3947 ms 499724 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 201692 KB Output is correct
2 Correct 176 ms 211120 KB Output is correct
3 Correct 160 ms 209972 KB Output is correct
4 Correct 171 ms 209732 KB Output is correct
5 Correct 90 ms 200724 KB Output is correct
6 Correct 130 ms 209676 KB Output is correct
7 Correct 137 ms 201740 KB Output is correct
8 Correct 149 ms 211120 KB Output is correct
9 Correct 130 ms 209868 KB Output is correct
10 Correct 164 ms 209636 KB Output is correct
11 Correct 87 ms 200656 KB Output is correct
12 Correct 146 ms 209612 KB Output is correct
13 Correct 158 ms 209348 KB Output is correct
14 Correct 126 ms 209484 KB Output is correct
15 Correct 126 ms 209356 KB Output is correct
16 Correct 137 ms 208756 KB Output is correct
17 Correct 141 ms 207980 KB Output is correct
18 Correct 126 ms 209120 KB Output is correct
19 Correct 86 ms 199980 KB Output is correct
20 Correct 87 ms 199968 KB Output is correct
21 Correct 89 ms 199984 KB Output is correct
22 Correct 136 ms 201740 KB Output is correct
23 Correct 141 ms 211060 KB Output is correct
24 Correct 134 ms 209916 KB Output is correct
25 Correct 165 ms 209612 KB Output is correct
26 Correct 89 ms 200764 KB Output is correct
27 Correct 134 ms 209692 KB Output is correct
28 Correct 126 ms 209424 KB Output is correct
29 Correct 133 ms 209512 KB Output is correct
30 Correct 124 ms 209368 KB Output is correct
31 Correct 136 ms 208788 KB Output is correct
32 Correct 122 ms 208024 KB Output is correct
33 Correct 135 ms 209304 KB Output is correct
34 Correct 1107 ms 254108 KB Output is correct
35 Correct 1165 ms 248752 KB Output is correct
36 Correct 1241 ms 250904 KB Output is correct
37 Correct 1060 ms 256900 KB Output is correct
38 Correct 1101 ms 255536 KB Output is correct
39 Correct 5643 ms 250160 KB Output is correct
40 Correct 3691 ms 250572 KB Output is correct
41 Correct 2076 ms 250028 KB Output is correct
42 Correct 1113 ms 255704 KB Output is correct
43 Correct 1247 ms 256784 KB Output is correct
44 Correct 1205 ms 258512 KB Output is correct
45 Correct 1247 ms 253064 KB Output is correct
46 Correct 1048 ms 255372 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 201692 KB Output is correct
2 Correct 176 ms 211120 KB Output is correct
3 Correct 160 ms 209972 KB Output is correct
4 Correct 171 ms 209732 KB Output is correct
5 Correct 90 ms 200724 KB Output is correct
6 Correct 130 ms 209676 KB Output is correct
7 Correct 137 ms 201740 KB Output is correct
8 Correct 149 ms 211120 KB Output is correct
9 Correct 130 ms 209868 KB Output is correct
10 Correct 164 ms 209636 KB Output is correct
11 Correct 87 ms 200656 KB Output is correct
12 Correct 146 ms 209612 KB Output is correct
13 Correct 158 ms 209348 KB Output is correct
14 Correct 126 ms 209484 KB Output is correct
15 Correct 126 ms 209356 KB Output is correct
16 Correct 137 ms 208756 KB Output is correct
17 Correct 141 ms 207980 KB Output is correct
18 Correct 126 ms 209120 KB Output is correct
19 Correct 138 ms 201740 KB Output is correct
20 Correct 142 ms 211120 KB Output is correct
21 Correct 139 ms 209972 KB Output is correct
22 Correct 160 ms 209708 KB Output is correct
23 Correct 89 ms 200708 KB Output is correct
24 Correct 131 ms 209656 KB Output is correct
25 Correct 126 ms 209376 KB Output is correct
26 Correct 128 ms 209464 KB Output is correct
27 Correct 130 ms 209452 KB Output is correct
28 Correct 144 ms 208812 KB Output is correct
29 Correct 132 ms 207964 KB Output is correct
30 Correct 128 ms 209140 KB Output is correct
31 Correct 1110 ms 257588 KB Output is correct
32 Correct 1055 ms 264072 KB Output is correct
33 Correct 984 ms 259528 KB Output is correct
34 Correct 844 ms 262012 KB Output is correct
35 Runtime error 3947 ms 499724 KB Execution killed with signal 6
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 201692 KB Output is correct
2 Correct 176 ms 211120 KB Output is correct
3 Correct 160 ms 209972 KB Output is correct
4 Correct 171 ms 209732 KB Output is correct
5 Correct 90 ms 200724 KB Output is correct
6 Correct 130 ms 209676 KB Output is correct
7 Correct 137 ms 201740 KB Output is correct
8 Correct 149 ms 211120 KB Output is correct
9 Correct 130 ms 209868 KB Output is correct
10 Correct 164 ms 209636 KB Output is correct
11 Correct 87 ms 200656 KB Output is correct
12 Correct 146 ms 209612 KB Output is correct
13 Correct 158 ms 209348 KB Output is correct
14 Correct 126 ms 209484 KB Output is correct
15 Correct 126 ms 209356 KB Output is correct
16 Correct 137 ms 208756 KB Output is correct
17 Correct 141 ms 207980 KB Output is correct
18 Correct 126 ms 209120 KB Output is correct
19 Correct 138 ms 201740 KB Output is correct
20 Correct 142 ms 211120 KB Output is correct
21 Correct 139 ms 209972 KB Output is correct
22 Correct 160 ms 209708 KB Output is correct
23 Correct 89 ms 200708 KB Output is correct
24 Correct 131 ms 209656 KB Output is correct
25 Correct 126 ms 209376 KB Output is correct
26 Correct 128 ms 209464 KB Output is correct
27 Correct 130 ms 209452 KB Output is correct
28 Correct 144 ms 208812 KB Output is correct
29 Correct 132 ms 207964 KB Output is correct
30 Correct 128 ms 209140 KB Output is correct
31 Correct 1110 ms 257588 KB Output is correct
32 Correct 1055 ms 264072 KB Output is correct
33 Correct 984 ms 259528 KB Output is correct
34 Correct 844 ms 262012 KB Output is correct
35 Runtime error 3947 ms 499724 KB Execution killed with signal 6
36 Halted 0 ms 0 KB -