Submission #714566

#	Time	Username	Problem	Language	Result	Execution time	Memory
714566		parsadox2	Toll (BOI17_toll)	C++14	100 / 100	1118 ms	6220 KiB

toll

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 5e4 + 10 , maxsq = 2 , maxk = 7 , inf = 1e9;
int n , m , q , k , dis[maxn] , dis_jmp[maxn][maxk];
vector <pair<int , int>> adj[maxn];
vector <int> vec;

void Relax()
{
	for(auto u : vec)   dis[u] = inf;
	vec.clear();
}

void find_nex(int now , int to)
{
	int l = now * k , r = min(n , l + k);
	for(int i = l ; i < r ; i++)  vec.pb(i);
	if(now == to)  return;
	for(int i = l ; i < r ; i++)
		for(auto u : adj[i])
			dis[u.F] = min(dis[u.F] , dis[i] + u.S);
	find_nex(now + 1 , to);
}

void Build(int num)
{
	int l = num * k , r = min(n , l + k);
	int l2 = (num + maxsq) * k;
	for(int i = l ; i < r ; i++)
	{
		dis[i] = 0;
		find_nex(num , num + maxsq);
		for(int j = 0 ; j < k ; j++)
			dis_jmp[i][j] = dis[l2 + j];
		Relax();
	}
}

void jmp_nex(int a , int b)
{
	int l = a * k , r = min(n , l + k) , l2 = (a + maxsq) * k;
	for(int i = l ; i < r ; i++)  vec.pb(i);
	if(a == b)  return;
	for(int i = l ; i < r ; i++)
		for(int j = 0 ; j < k ; j++)
			dis[l2 + j] = min(dis[l2 + j] , dis[i] + dis_jmp[i][j]);
	jmp_nex(a + maxsq , b);
}

void Find_dis(int a , int b)
{
	int tmp = (a + maxsq) / maxsq;
	tmp *= maxsq;
	if(b <= tmp)
	{
		find_nex(a , b);
		return;
	}
	find_nex(a , tmp);
	int tmp2 = b / maxsq;
	tmp2 *= maxsq;
	jmp_nex(tmp , tmp2);
	find_nex(tmp2 , b);
}

int32_t main()
{
	fast;
	cin >> k >> n >> m >> q;
	for(int i = 0 ; i < n ; i++)  dis[i] = inf;
	for(int i = 0 ; i < m ; i++)
	{
		int v , u , c;  cin >> v >> u >> c;
		adj[v].pb({u , c});
	}
	for(int i = 0 ; (i + maxsq) * k < n ; i += maxsq)  Build(i);
	while(q--)
	{
		int v , u;  cin >> v >> u;
		if(v > u)
		{
			cout << -1 << '\n';
			continue;
		}
		dis[v] = 0;
		vec.pb(v);
		Find_dis(v / k , u / k);
		cout << (dis[u] == inf ? -1 : dis[u]) << '\n';
		Relax();
	}
	return 0;
}

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