oj.uz

Submission #771787

# Submission time Handle Problem Language Result Execution time Memory
771787 2023-07-03T09:18:34 Z LittleCube From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 233236 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], 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';
	// }
	cerr << "update counter " << cnt << '\n';
	if (dis[N][0] >= 1e18)
		cout << "impossible\n";
	else
		cout << dis[N][0] << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 178248 KB Output is correct
2 Correct 149 ms 184564 KB Output is correct
3 Correct 132 ms 185016 KB Output is correct
4 Correct 436 ms 185180 KB Output is correct
5 Correct 100 ms 177376 KB Output is correct
6 Correct 136 ms 185004 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 178260 KB Output is correct
2 Correct 135 ms 184516 KB Output is correct
3 Correct 145 ms 185040 KB Output is correct
4 Correct 378 ms 185236 KB Output is correct
5 Correct 104 ms 177280 KB Output is correct
6 Correct 147 ms 185000 KB Output is correct
7 Correct 135 ms 184608 KB Output is correct
8 Correct 127 ms 184520 KB Output is correct
9 Correct 121 ms 184436 KB Output is correct
10 Correct 187 ms 184896 KB Output is correct
11 Correct 144 ms 184560 KB Output is correct
12 Correct 131 ms 184632 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 178260 KB Output is correct
2 Correct 135 ms 184516 KB Output is correct
3 Correct 145 ms 185040 KB Output is correct
4 Correct 378 ms 185236 KB Output is correct
5 Correct 104 ms 177280 KB Output is correct
6 Correct 147 ms 185000 KB Output is correct
7 Correct 135 ms 184608 KB Output is correct
8 Correct 127 ms 184520 KB Output is correct
9 Correct 121 ms 184436 KB Output is correct
10 Correct 187 ms 184896 KB Output is correct
11 Correct 144 ms 184560 KB Output is correct
12 Correct 131 ms 184632 KB Output is correct
13 Correct 363 ms 179080 KB Output is correct
14 Correct 133 ms 185696 KB Output is correct
15 Correct 139 ms 184980 KB Output is correct
16 Correct 395 ms 185212 KB Output is correct
17 Correct 99 ms 177332 KB Output is correct
18 Correct 141 ms 185012 KB Output is correct
19 Correct 146 ms 184628 KB Output is correct
20 Correct 134 ms 184532 KB Output is correct
21 Correct 127 ms 184396 KB Output is correct
22 Correct 189 ms 184904 KB Output is correct
23 Correct 142 ms 184556 KB Output is correct
24 Correct 157 ms 184732 KB Output is correct
25 Correct 1077 ms 229756 KB Output is correct
26 Correct 1137 ms 233236 KB Output is correct
27 Correct 1030 ms 228168 KB Output is correct
28 Correct 875 ms 231396 KB Output is correct
29 Execution timed out 6025 ms 224372 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 178260 KB Output is correct
2 Correct 135 ms 184516 KB Output is correct
3 Correct 145 ms 185040 KB Output is correct
4 Correct 378 ms 185236 KB Output is correct
5 Correct 104 ms 177280 KB Output is correct
6 Correct 147 ms 185000 KB Output is correct
7 Correct 135 ms 184608 KB Output is correct
8 Correct 127 ms 184520 KB Output is correct
9 Correct 121 ms 184436 KB Output is correct
10 Correct 187 ms 184896 KB Output is correct
11 Correct 144 ms 184560 KB Output is correct
12 Correct 131 ms 184632 KB Output is correct
13 Correct 363 ms 179080 KB Output is correct
14 Correct 133 ms 185696 KB Output is correct
15 Correct 139 ms 184980 KB Output is correct
16 Correct 395 ms 185212 KB Output is correct
17 Correct 99 ms 177332 KB Output is correct
18 Correct 141 ms 185012 KB Output is correct
19 Correct 146 ms 184628 KB Output is correct
20 Correct 134 ms 184532 KB Output is correct
21 Correct 127 ms 184396 KB Output is correct
22 Correct 189 ms 184904 KB Output is correct
23 Correct 142 ms 184556 KB Output is correct
24 Correct 157 ms 184732 KB Output is correct
25 Correct 1077 ms 229756 KB Output is correct
26 Correct 1137 ms 233236 KB Output is correct
27 Correct 1030 ms 228168 KB Output is correct
28 Correct 875 ms 231396 KB Output is correct
29 Execution timed out 6025 ms 224372 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 178248 KB Output is correct
2 Correct 149 ms 184564 KB Output is correct
3 Correct 132 ms 185016 KB Output is correct
4 Correct 436 ms 185180 KB Output is correct
5 Correct 100 ms 177376 KB Output is correct
6 Correct 136 ms 185004 KB Output is correct
7 Correct 358 ms 178260 KB Output is correct
8 Correct 135 ms 184516 KB Output is correct
9 Correct 145 ms 185040 KB Output is correct
10 Correct 378 ms 185236 KB Output is correct
11 Correct 104 ms 177280 KB Output is correct
12 Correct 147 ms 185000 KB Output is correct
13 Correct 135 ms 184608 KB Output is correct
14 Correct 127 ms 184520 KB Output is correct
15 Correct 121 ms 184436 KB Output is correct
16 Correct 187 ms 184896 KB Output is correct
17 Correct 144 ms 184560 KB Output is correct
18 Correct 131 ms 184632 KB Output is correct
19 Correct 94 ms 176456 KB Output is correct
20 Correct 98 ms 176504 KB Output is correct
21 Correct 92 ms 176400 KB Output is correct
22 Correct 366 ms 178832 KB Output is correct
23 Correct 149 ms 185700 KB Output is correct
24 Correct 162 ms 185028 KB Output is correct
25 Correct 381 ms 185220 KB Output is correct
26 Correct 103 ms 177384 KB Output is correct
27 Correct 143 ms 185024 KB Output is correct
28 Correct 130 ms 184592 KB Output is correct
29 Correct 134 ms 184580 KB Output is correct
30 Correct 132 ms 184472 KB Output is correct
31 Correct 189 ms 184876 KB Output is correct
32 Correct 133 ms 184600 KB Output is correct
33 Correct 142 ms 184608 KB Output is correct
34 Correct 1135 ms 228804 KB Output is correct
35 Correct 1266 ms 225256 KB Output is correct
36 Correct 1275 ms 225128 KB Output is correct
37 Correct 1004 ms 229572 KB Output is correct
38 Correct 1183 ms 227144 KB Output is correct
39 Execution timed out 6050 ms 224092 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 178248 KB Output is correct
2 Correct 149 ms 184564 KB Output is correct
3 Correct 132 ms 185016 KB Output is correct
4 Correct 436 ms 185180 KB Output is correct
5 Correct 100 ms 177376 KB Output is correct
6 Correct 136 ms 185004 KB Output is correct
7 Correct 358 ms 178260 KB Output is correct
8 Correct 135 ms 184516 KB Output is correct
9 Correct 145 ms 185040 KB Output is correct
10 Correct 378 ms 185236 KB Output is correct
11 Correct 104 ms 177280 KB Output is correct
12 Correct 147 ms 185000 KB Output is correct
13 Correct 135 ms 184608 KB Output is correct
14 Correct 127 ms 184520 KB Output is correct
15 Correct 121 ms 184436 KB Output is correct
16 Correct 187 ms 184896 KB Output is correct
17 Correct 144 ms 184560 KB Output is correct
18 Correct 131 ms 184632 KB Output is correct
19 Correct 363 ms 179080 KB Output is correct
20 Correct 133 ms 185696 KB Output is correct
21 Correct 139 ms 184980 KB Output is correct
22 Correct 395 ms 185212 KB Output is correct
23 Correct 99 ms 177332 KB Output is correct
24 Correct 141 ms 185012 KB Output is correct
25 Correct 146 ms 184628 KB Output is correct
26 Correct 134 ms 184532 KB Output is correct
27 Correct 127 ms 184396 KB Output is correct
28 Correct 189 ms 184904 KB Output is correct
29 Correct 142 ms 184556 KB Output is correct
30 Correct 157 ms 184732 KB Output is correct
31 Correct 1077 ms 229756 KB Output is correct
32 Correct 1137 ms 233236 KB Output is correct
33 Correct 1030 ms 228168 KB Output is correct
34 Correct 875 ms 231396 KB Output is correct
35 Execution timed out 6025 ms 224372 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 178248 KB Output is correct
2 Correct 149 ms 184564 KB Output is correct
3 Correct 132 ms 185016 KB Output is correct
4 Correct 436 ms 185180 KB Output is correct
5 Correct 100 ms 177376 KB Output is correct
6 Correct 136 ms 185004 KB Output is correct
7 Correct 358 ms 178260 KB Output is correct
8 Correct 135 ms 184516 KB Output is correct
9 Correct 145 ms 185040 KB Output is correct
10 Correct 378 ms 185236 KB Output is correct
11 Correct 104 ms 177280 KB Output is correct
12 Correct 147 ms 185000 KB Output is correct
13 Correct 135 ms 184608 KB Output is correct
14 Correct 127 ms 184520 KB Output is correct
15 Correct 121 ms 184436 KB Output is correct
16 Correct 187 ms 184896 KB Output is correct
17 Correct 144 ms 184560 KB Output is correct
18 Correct 131 ms 184632 KB Output is correct
19 Correct 363 ms 179080 KB Output is correct
20 Correct 133 ms 185696 KB Output is correct
21 Correct 139 ms 184980 KB Output is correct
22 Correct 395 ms 185212 KB Output is correct
23 Correct 99 ms 177332 KB Output is correct
24 Correct 141 ms 185012 KB Output is correct
25 Correct 146 ms 184628 KB Output is correct
26 Correct 134 ms 184532 KB Output is correct
27 Correct 127 ms 184396 KB Output is correct
28 Correct 189 ms 184904 KB Output is correct
29 Correct 142 ms 184556 KB Output is correct
30 Correct 157 ms 184732 KB Output is correct
31 Correct 1077 ms 229756 KB Output is correct
32 Correct 1137 ms 233236 KB Output is correct
33 Correct 1030 ms 228168 KB Output is correct
34 Correct 875 ms 231396 KB Output is correct
35 Execution timed out 6025 ms 224372 KB Time limit exceeded
36 Halted 0 ms 0 KB -