Submission #550496

#	Time	Username	Problem	Language	Result	Execution time	Memory
550496		LittleCube	From Hacks to Snitches (BOI21_watchmen)	C++14	0 / 100	69 ms	25856 KiB

watchmen

#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] && !s && 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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20