oj.uz

Submission #550502

# Submission time Handle Problem Language Result Execution time Memory
550502 2022-04-18T09:57:53 Z LittleCube From Hacks to Snitches (BOI21_watchmen) C++14
0 / 100
 71 ms 25516 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, M, K, vis[250005][2], dis[250002][2], p[250005], r[250005];
vector<int> E[250005];
vector<pii> dv[500005];

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);
	}
	cin >> K;
	for(int i = 1; i <= K; i++)
	{
		int P, u;
		cin >> P;
		for(int j = 0; j < P; j++)
		{
			cin >> u;
			p[u] = P, r[u] = j;
		}
	}
	for(int i = 1; i <= N; i++)
		dis[i][0] = dis[i][1] = 1e9;
	dis[1][0] = 0;
	dv[0].emplace_back(pii(1, 0));
	for(int d = 0; d <= 2 * N; d++)
	{
		while(!dv[d].empty())
		{
			auto [u, s] = dv[d].back();
			dv[d].pop_back();
			if(dis[u][s] < d)
				continue;
			for(auto v : E[u])
			{
				int t = (p[v] == 0 ? -1 : (r[v] - (d % p[v]) + p[v]) % p[v]),
					tt = (p[v] == 0 ? -1 : (r[v] - ((d + 1) % p[v]) + p[v]) % p[v]);
				if(!p[v])
					if(dis[v][0] > dis[u][s] + 1)
					{
						dis[v][0] = dis[u][s] + 1;
						dv[d + 1].emplace_back(pii(v, 0));
					}
				if(p[v] && t >= 2)
					if(dis[v][tt <= 2] > dis[u][s] + 1)
					{
						dis[v][tt <= 2] = dis[u][s] + 1;
						dv[d + 1].emplace_back(pii(v, tt <= 2));
					}
				if(p[v] && !p[u] && t <= 1)
					if(dis[v][p[v] == 3] > dis[u][s] + 1 + t)
					{
						dis[v][p[v] == 3] = dis[u][s] + 1 + t;
						dv[d + 1 + t].emplace_back(pii(v, p[v] == 3));
					}
			}
		}
	}
	//for(int i = 1; i <= N; i++)
	//	cout << dis[i][0] << " " << dis[i][1] << '\n';
	if(dis[N][0] >= 1e9)
		cout << "impossible\n";
	else cout << dis[N][0];
}

Compilation message

watchmen.cpp: In function 'int main()':
watchmen.cpp:44:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |    auto [u, s] = dv[d].back();
      |         ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18904 KB Output is correct
2 Incorrect 71 ms 25516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18900 KB Output is correct
2 Incorrect 56 ms 25420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18900 KB Output is correct
2 Incorrect 56 ms 25420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18900 KB Output is correct
2 Incorrect 56 ms 25420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18904 KB Output is correct
2 Incorrect 71 ms 25516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18904 KB Output is correct
2 Incorrect 71 ms 25516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18904 KB Output is correct
2 Incorrect 71 ms 25516 KB Output isn't correct
3 Halted 0 ms 0 KB -