Submission #817696

#	Time	Username	Problem	Language	Result	Execution time	Memory
817696		MohamedAhmed04	From Hacks to Snitches (BOI21_watchmen)	C++17	35 / 100	6087 ms	311436 KiB

watchmen

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std ;

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

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][K] ;

int calc[MAX][205] ;

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}) ;
				}
			}
		}
	}
}

void solve2(int src)
{
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 0 ; j < K ; ++j)
			dist[i][j] = inf ;
	}
	queue< pair<int , int> >q ;
	dist[src][0] = 0 ;
	q.push({src , 0}) ;
	while(!q.empty())
	{
		pair<int , int>p = q.front() ;
		q.pop() ;
		int node = p.first , wait = p.second ;
		int cost = dist[node][wait] , x = watch[node] ;
		if(node == n)
			return ;
		if((!x) || (v[x][calc[cost + 1][cycle_sz[x]]] != node))
		{
			if(wait+1 < K && dist[node][wait+1] == inf)
			{
				dist[node][wait+1] = cost + 1 ;
				q.push({node , wait+1}) ;
			}
		}
		for(auto &child : adj[node])
		{
			int child2 = child ;
			int cost2 = cost + 1 ;
			x = watch[child] ;
			if(x > 0 && v[x][calc[cost2 - 1][cycle_sz[x]]] == child2 && v[x][calc[cost2][cycle_sz[x]]] == node)
				continue ;
			if(x > 0 && v[x][calc[cost2][cycle_sz[x]]] == child2)
				continue ;
			if(dist[child2][wait] == inf)
			{
				dist[child2][wait] = cost2 ;
				q.push({child2 , wait}) ;
			}
		}
	}
}

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 ;
		}
	}
	bool flag = true ;
	for(int i = 1 ; i <= n ; ++i)
	{
		for(auto &child : adj[i])
			flag &= (watch[i] == 0 || watch[child] == 0 || watch[i] == watch[child]) ;
	}
	if(flag) //no corridor connects two two different routes
	{
		solve(1) ;
		if(dist[n][0] == inf)
			cout<<"impossible\n" ;
		else
			cout<<dist[n][0]<<"\n" ;
	}
	else
	{
		for(int j = 1 ; j < 205 ; ++j)
		{
			calc[0][j] = 0 ;
			for(int i = 1 ; i < n + 1000 ; ++i)
			{
				calc[i][j] = calc[i-1][j] + 1 ;
				if(calc[i][j] == j)
					calc[i][j] = 0 ;
			}
		}
		solve2(1) ;
		int ans = inf ;
		for(int i = 0 ; i < K ; ++i)
			ans = min(ans , dist[n][i]) ;
		if(ans == inf)
			cout<<"impossible\n" ;
		else
			cout<<ans<<"\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