Submission #817653

#	Time	Username	Problem	Language	Result	Execution time	Memory
817653		MohamedAhmed04	From Hacks to Snitches (BOI21_watchmen)	C++14	35 / 100	1103 ms	68580 KiB

watchmen

#include <bits/stdc++.h>

using namespace std ;

const int inf = 1e9 ;
const int MAX = 3e5 + 10 ;

int arr[MAX] ;
int n , m , k ;

vector< vector<int> >adj(MAX) ;

vector<int>v[MAX] ;
int watch[MAX] , cycle_sz[MAX] , id[MAX] ;

int dist[MAX][2] ;

bool check(int node , int child , int tim)
{
	assert(watch[child] != 0) ;
	int x = watch[node] ;
	int tim_node = 2e9 ;
	if(watch[node])
	{
		int cur = tim % cycle_sz[x] ;
		tim_node = tim + (id[node] - cur + cycle_sz[x]) % cycle_sz[x] ;
	}
	int tim_child = -2e9 ;
	x = watch[child] ;
	int cur = tim % cycle_sz[x] ;
	tim_child = tim + (id[child] - cur + cycle_sz[x]) % cycle_sz[x] ;
	return (tim_child < tim_node-1 || (tim_child == tim_node - 1 && watch[child] != watch[node])) ;
}

void solve(int src)
{
	for(int i = 1 ; i <= n ; ++i)
		dist[i][0] = dist[i][1] = inf ;
	priority_queue< array<int , 3> , vector< array<int , 3> > , greater< array<int , 3> > >q ;
	dist[src][0] = 0 ;
	q.push({0 , src , 0}) ;
	while(!q.empty())
	{
		array<int , 3>a = q.top() ;
		q.pop() ;
		int node = a[1] , cost = a[0] , t = a[2] ;
		if(dist[node][t] < cost)
			continue ;
		for(auto &child : adj[node])
		{
			int child2 = child ;
			int cost2 = cost + 1 ;
			if((!watch[child2]))
			{
				if(cost2 < dist[child2][0])
				{
					dist[child2][0] = cost2 ;
					q.push({cost2 , child2 , 0}) ;
				}
				continue ;
			}
			int x = watch[child2] ;
			if(check(node , child2 , cost)) //handle waiting for some time
			{
				int cur = cost % cycle_sz[x] ;
				cost2 = cost + (id[child2] - cur + cycle_sz[x]) % cycle_sz[x] + 1 ; 
				if(cost2 < dist[child2][1])
				{
					dist[child2][1] = cost2 ;
					q.push({cost2 , child2 , 1}) ;
				}
			}
			cost2 = cost + 1 ;
			//handle corridor 
			if(v[x][(cost2 - 1) % cycle_sz[x]] == child2 && v[x][cost2 % cycle_sz[x]] == node)
				continue ;
			if(v[x][cost2 % cycle_sz[x]] != child2) //go without waiting
			{
				if(cost2 < dist[child2][t])
				{
					dist[child2][t] = cost2 ;
					q.push({cost2 , child2 , t}) ;
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m ;
	for(int i = 0 ; i < m ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	cin>>k ;
	for(int i = 1 ; i <= k ; ++i)
	{
		cin>>cycle_sz[i] ;
		v[i].resize(cycle_sz[i]) ;
		for(int j = 0 ; j < cycle_sz[i] ; ++j)
		{
			cin>>v[i][j] ;
			watch[v[i][j]] = i ;
			id[v[i][j]] = j ;
		}
	}
	solve(1) ;
	if(dist[n][0] == inf)
		cout<<"impossible\n" ;
	else
		cout<<dist[n][0]<<"\n" ;
	return 0 ;
}		

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20