Submission #381659

#	Time	Username	Problem	Language	Result	Execution time	Memory
381659		MohamedAhmed04	Toll (BOI17_toll)	C++14	100 / 100	125 ms	84588 KiB

toll

#include <bits/stdc++.h>

using namespace std ;

const int inf = 2e9 ;
const int MAX = 5e4 + 10 ;

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

int dist[MAX][17][5][5] , ans[5] , tmp[5] ;

void preprocess()
{
	for(int j = 1 ; j < 17 ; ++j)
	{
		for(int i = 0 ; i <= n/k ; ++i)
		{
			for(int k1 = 0 ; k1 < k ; ++k1)
			{
				for(int k2 = 0 ; k2 < k ; ++k2)
				{
					int jump = (1 << j) ;
					if((i + jump) * k + k2 >= n)
						continue ;
					dist[i][j][k1][k2] = inf ;
					int prv_jump = (1 << (j-1)) ;
					for(int k3 = 0 ; k3 < k ; ++k3)
					{
						if(dist[i][j-1][k1][k3] && dist[i+prv_jump][j-1][k3][k2])
							dist[i][j][k1][k2] = min(dist[i][j][k1][k2] , dist[i][j-1][k1][k3] + dist[i + prv_jump][j-1][k3][k2]) ;
					}
					if(dist[i][j][k1][k2] == inf)
						dist[i][j][k1][k2] = 0 ;
				}
			}
		}
	}
} 

int main()
{

	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>k>>n>>m>>q ;
	for(int i = 0 ; i < m ; ++i)
	{
		int x , y , z ;
		cin>>x>>y>>z ;
		dist[x/k][0][x%k][y%k] = z ;
	}
	preprocess() ;
	while(q--)
	{
		memset(ans , -1 , sizeof(ans)) ;
		int x , y ;
		cin>>x>>y ;
		int a = x/k , b = y/k ;
		ans[x%k] = 0 ;
		for(int j = 16 ; j >= 0 ; --j)
		{
			if((a + (1 << j)) > b)
				continue ;
			for(int k1 = 0 ; k1 < k ; ++k1)
				tmp[k1] = ans[k1] ;
			for(int k2 = 0 ; k2 < k ; ++k2)
			{
				ans[k2] = -1 ;
				for(int k1 = 0 ; k1 < k ; ++k1)
				{
					if(dist[a][j][k1][k2] && tmp[k1] != -1)
					{
						if(ans[k2] == -1)
							ans[k2] = dist[a][j][k1][k2] + tmp[k1] ;
						else
							ans[k2] = min(ans[k2] , dist[a][j][k1][k2] + tmp[k1]) ;
					}
				}
			}
			a += (1 << j) ;
		}
		cout<<ans[y%k]<<"\n" ;
	}
	return 0 ;
}		

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44