oj.uz

Submission #771791

# Submission time Handle Problem Language Result Execution time Memory
771791 2023-07-03T09:22:35 Z LittleCube From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 283804 KB 
#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], mp[2000];
ll cnt = 0;
vector<int> v[2000];
vector<ll> dis[2500005];
vector<bitset<128>> vis[2500005];
vector<int> E[2500005];

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;
	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 (l[v] == 1 && d + 1 < dis[v][0])
				{
					dis[v][0] = d + 1;
					pq.push(state{d + 1, v, 0, 0});
				}
				else if (l[v] > 1)
				{
					if (!goodmove(u, v, d + 1) && l[u] % l[v] == 0)
						continue;
					pq.push(state{d, u, k, v});
				}

			int rem = (d + 1) % l[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
		{
			cnt++;
			// u -> b
			int rem = (d + 1) % l[b];
			if (vis[b][rem][mp[l[u]]])
				continue;
			if (goodmove(u, b, d + 1))
			{
				if (dis[b][rem] > d + 1)
				{
					dis[b][rem] = d + 1;
					pq.push(state{d + 1, b, rem, 0});
				}
			}
			vis[b][rem][mp[l[u]]] = 1;
			pq.push(state{d + l[u], u, k, 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 353 ms 178196 KB Output is correct
2 Correct 127 ms 184572 KB Output is correct
3 Correct 128 ms 183920 KB Output is correct
4 Correct 393 ms 184064 KB Output is correct
5 Correct 90 ms 177344 KB Output is correct
6 Correct 139 ms 183856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 178224 KB Output is correct
2 Correct 137 ms 184588 KB Output is correct
3 Correct 143 ms 183812 KB Output is correct
4 Correct 381 ms 184000 KB Output is correct
5 Correct 89 ms 177380 KB Output is correct
6 Correct 142 ms 183872 KB Output is correct
7 Correct 115 ms 183448 KB Output is correct
8 Correct 114 ms 183444 KB Output is correct
9 Correct 110 ms 183232 KB Output is correct
10 Correct 188 ms 183820 KB Output is correct
11 Correct 124 ms 183424 KB Output is correct
12 Correct 119 ms 183436 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 178224 KB Output is correct
2 Correct 137 ms 184588 KB Output is correct
3 Correct 143 ms 183812 KB Output is correct
4 Correct 381 ms 184000 KB Output is correct
5 Correct 89 ms 177380 KB Output is correct
6 Correct 142 ms 183872 KB Output is correct
7 Correct 115 ms 183448 KB Output is correct
8 Correct 114 ms 183444 KB Output is correct
9 Correct 110 ms 183232 KB Output is correct
10 Correct 188 ms 183820 KB Output is correct
11 Correct 124 ms 183424 KB Output is correct
12 Correct 119 ms 183436 KB Output is correct
13 Correct 349 ms 178288 KB Output is correct
14 Correct 125 ms 184580 KB Output is correct
15 Correct 129 ms 183880 KB Output is correct
16 Correct 376 ms 184088 KB Output is correct
17 Correct 84 ms 177352 KB Output is correct
18 Correct 127 ms 183860 KB Output is correct
19 Correct 114 ms 183456 KB Output is correct
20 Correct 117 ms 183380 KB Output is correct
21 Correct 124 ms 183304 KB Output is correct
22 Correct 180 ms 183700 KB Output is correct
23 Correct 122 ms 183472 KB Output is correct
24 Correct 119 ms 183464 KB Output is correct
25 Correct 1075 ms 229516 KB Output is correct
26 Correct 1004 ms 233104 KB Output is correct
27 Correct 949 ms 228148 KB Output is correct
28 Correct 795 ms 231116 KB Output is correct
29 Execution timed out 6045 ms 224140 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 178224 KB Output is correct
2 Correct 137 ms 184588 KB Output is correct
3 Correct 143 ms 183812 KB Output is correct
4 Correct 381 ms 184000 KB Output is correct
5 Correct 89 ms 177380 KB Output is correct
6 Correct 142 ms 183872 KB Output is correct
7 Correct 115 ms 183448 KB Output is correct
8 Correct 114 ms 183444 KB Output is correct
9 Correct 110 ms 183232 KB Output is correct
10 Correct 188 ms 183820 KB Output is correct
11 Correct 124 ms 183424 KB Output is correct
12 Correct 119 ms 183436 KB Output is correct
13 Correct 349 ms 178288 KB Output is correct
14 Correct 125 ms 184580 KB Output is correct
15 Correct 129 ms 183880 KB Output is correct
16 Correct 376 ms 184088 KB Output is correct
17 Correct 84 ms 177352 KB Output is correct
18 Correct 127 ms 183860 KB Output is correct
19 Correct 114 ms 183456 KB Output is correct
20 Correct 117 ms 183380 KB Output is correct
21 Correct 124 ms 183304 KB Output is correct
22 Correct 180 ms 183700 KB Output is correct
23 Correct 122 ms 183472 KB Output is correct
24 Correct 119 ms 183464 KB Output is correct
25 Correct 1075 ms 229516 KB Output is correct
26 Correct 1004 ms 233104 KB Output is correct
27 Correct 949 ms 228148 KB Output is correct
28 Correct 795 ms 231116 KB Output is correct
29 Execution timed out 6045 ms 224140 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 178196 KB Output is correct
2 Correct 127 ms 184572 KB Output is correct
3 Correct 128 ms 183920 KB Output is correct
4 Correct 393 ms 184064 KB Output is correct
5 Correct 90 ms 177344 KB Output is correct
6 Correct 139 ms 183856 KB Output is correct
7 Correct 354 ms 178224 KB Output is correct
8 Correct 137 ms 184588 KB Output is correct
9 Correct 143 ms 183812 KB Output is correct
10 Correct 381 ms 184000 KB Output is correct
11 Correct 89 ms 177380 KB Output is correct
12 Correct 142 ms 183872 KB Output is correct
13 Correct 115 ms 183448 KB Output is correct
14 Correct 114 ms 183444 KB Output is correct
15 Correct 110 ms 183232 KB Output is correct
16 Correct 188 ms 183820 KB Output is correct
17 Correct 124 ms 183424 KB Output is correct
18 Correct 119 ms 183436 KB Output is correct
19 Correct 78 ms 176492 KB Output is correct
20 Correct 77 ms 176460 KB Output is correct
21 Correct 77 ms 176508 KB Output is correct
22 Correct 349 ms 178212 KB Output is correct
23 Correct 126 ms 184480 KB Output is correct
24 Correct 127 ms 183828 KB Output is correct
25 Correct 381 ms 184128 KB Output is correct
26 Correct 85 ms 177292 KB Output is correct
27 Correct 131 ms 183908 KB Output is correct
28 Correct 115 ms 183440 KB Output is correct
29 Correct 115 ms 183404 KB Output is correct
30 Correct 111 ms 183312 KB Output is correct
31 Correct 177 ms 183728 KB Output is correct
32 Correct 127 ms 183432 KB Output is correct
33 Correct 119 ms 183480 KB Output is correct
34 Correct 1208 ms 228916 KB Output is correct
35 Correct 1178 ms 224956 KB Output is correct
36 Correct 1174 ms 225032 KB Output is correct
37 Correct 1016 ms 229468 KB Output is correct
38 Correct 1012 ms 226880 KB Output is correct
39 Execution timed out 6039 ms 283804 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 178196 KB Output is correct
2 Correct 127 ms 184572 KB Output is correct
3 Correct 128 ms 183920 KB Output is correct
4 Correct 393 ms 184064 KB Output is correct
5 Correct 90 ms 177344 KB Output is correct
6 Correct 139 ms 183856 KB Output is correct
7 Correct 354 ms 178224 KB Output is correct
8 Correct 137 ms 184588 KB Output is correct
9 Correct 143 ms 183812 KB Output is correct
10 Correct 381 ms 184000 KB Output is correct
11 Correct 89 ms 177380 KB Output is correct
12 Correct 142 ms 183872 KB Output is correct
13 Correct 115 ms 183448 KB Output is correct
14 Correct 114 ms 183444 KB Output is correct
15 Correct 110 ms 183232 KB Output is correct
16 Correct 188 ms 183820 KB Output is correct
17 Correct 124 ms 183424 KB Output is correct
18 Correct 119 ms 183436 KB Output is correct
19 Correct 349 ms 178288 KB Output is correct
20 Correct 125 ms 184580 KB Output is correct
21 Correct 129 ms 183880 KB Output is correct
22 Correct 376 ms 184088 KB Output is correct
23 Correct 84 ms 177352 KB Output is correct
24 Correct 127 ms 183860 KB Output is correct
25 Correct 114 ms 183456 KB Output is correct
26 Correct 117 ms 183380 KB Output is correct
27 Correct 124 ms 183304 KB Output is correct
28 Correct 180 ms 183700 KB Output is correct
29 Correct 122 ms 183472 KB Output is correct
30 Correct 119 ms 183464 KB Output is correct
31 Correct 1075 ms 229516 KB Output is correct
32 Correct 1004 ms 233104 KB Output is correct
33 Correct 949 ms 228148 KB Output is correct
34 Correct 795 ms 231116 KB Output is correct
35 Execution timed out 6045 ms 224140 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 178196 KB Output is correct
2 Correct 127 ms 184572 KB Output is correct
3 Correct 128 ms 183920 KB Output is correct
4 Correct 393 ms 184064 KB Output is correct
5 Correct 90 ms 177344 KB Output is correct
6 Correct 139 ms 183856 KB Output is correct
7 Correct 354 ms 178224 KB Output is correct
8 Correct 137 ms 184588 KB Output is correct
9 Correct 143 ms 183812 KB Output is correct
10 Correct 381 ms 184000 KB Output is correct
11 Correct 89 ms 177380 KB Output is correct
12 Correct 142 ms 183872 KB Output is correct
13 Correct 115 ms 183448 KB Output is correct
14 Correct 114 ms 183444 KB Output is correct
15 Correct 110 ms 183232 KB Output is correct
16 Correct 188 ms 183820 KB Output is correct
17 Correct 124 ms 183424 KB Output is correct
18 Correct 119 ms 183436 KB Output is correct
19 Correct 349 ms 178288 KB Output is correct
20 Correct 125 ms 184580 KB Output is correct
21 Correct 129 ms 183880 KB Output is correct
22 Correct 376 ms 184088 KB Output is correct
23 Correct 84 ms 177352 KB Output is correct
24 Correct 127 ms 183860 KB Output is correct
25 Correct 114 ms 183456 KB Output is correct
26 Correct 117 ms 183380 KB Output is correct
27 Correct 124 ms 183304 KB Output is correct
28 Correct 180 ms 183700 KB Output is correct
29 Correct 122 ms 183472 KB Output is correct
30 Correct 119 ms 183464 KB Output is correct
31 Correct 1075 ms 229516 KB Output is correct
32 Correct 1004 ms 233104 KB Output is correct
33 Correct 949 ms 228148 KB Output is correct
34 Correct 795 ms 231116 KB Output is correct
35 Execution timed out 6045 ms 224140 KB Time limit exceeded
36 Halted 0 ms 0 KB -