Submission #924616

#	Time	Username	Problem	Language	Result	Execution time	Memory
924616		KaleemRazaSyed	Toll (BOI17_toll)	C++17	100 / 100	174 ms	44884 KiB

toll

#include<iostream>
 
using namespace std;
 
typedef long long ll;
 
const int N = 50001, C = 6, K = 17;
const ll inf = 1e18;
ll G[N][C];
ll dis[N][C][K];
 
int main()
{
  int k, n, m, o;
  cin >> k >> n >> m >> o;
 
  for(int i = 0; i < n; i++)
    for(int j = 0; j < k; j++)
      G[i][j] = inf;
 
  for(int i = 0; i < n; i ++)
    for(int j = 0; j < k; j++)
      for(int l = 0; l < K; l++)
	dis[i][j][k] = inf;
  
  for(int i = 0; i < m; i++)
    {
      ll a, b, t;
      cin >> a >> b >> t;
      G[a][b % k] = min(G[a][b % k], t);
    }
 
  for(int i = n - 1; i >= 0; i--)
    {
      for(int j = 0; j < k; j++)
	dis[i][j][0] = G[i][j];
 
      for(int p = 1; p < K; p++)
	for(int j = 0; j < k && (1 << p) * k + i - i%k + j < n; j++)
	  {
	    ll mx = inf;
	    for(int l = 0; l < k; l++)
	      {
		int v = (1 << (p-1)) * k + i - i%k + l;
		if(v >= n) break;
		mx = min(mx, dis[i][l][p - 1] + dis[v][j][p-1]);
	      }
	    dis[i][j][p] = mx;
	  }
    }
  
  while(o--)
    {
      int a, b;
      cin >> a >> b;
      int d = (b / k) - (a / k);
      
      if(d == 0)
	{
	  cout << -1 << '\n';
	  continue;
	}
      ll dist[k], v[k];
      
      int f = __builtin_ctz(d);
      for(int i = 0; i < k; i++)
	{
	  dist[i] = dis[a][i][f];
	  v[i] = (a - a % k) + (1 << f) * k + i;
	}
 
      for(int l = f + 1; l < K; l++)
	if((1 << l) & d)
	  {
	    ll newD[k];
	    for(int i = 0; i < k; i++)
	      newD[i] = inf;
 
	    for(int i = 0; i < k; i++)
	      for(int j = 0; j < k; j++)
		newD[j] = min(dist[i] + dis[v[i]][j][l], newD[j]);
 
	    for(int i = 0; i < k; i++)
	      dist[i] = newD[i], v[i] += (1 << l) * k;
	  }
 
      cout << (dist[b % k] >= inf ? -1 : dist[b%k]) << '\n';
    }
  
  
  return 0;
}

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