제출 #924547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924547		KaleemRazaSyed	Toll (BOI17_toll)	C++17	0 / 100	92 ms	42700 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 < C; 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[C], v[C];
      
      int f = __builtin_ctz(d);
      for(int i = 0; i < C; i++)
	{
	  dist[i] = dis[a][i][f];
	  v[i] = (a - a % k) + (1 << f) * k + i;
	}
 
      d -= (1 << f);
 
      for(int b = f + 1; b < K; b++)
	if((1 << b) & 1)
	  {
	    ll newD[C];
	    for(int i = 0; i < C; i++)
	      newD[i] = inf;
 
	    for(int i = 0; i < C; i++)
	      for(int j = 0; j < C; j++)
		newD[j] = min(dist[i] + dis[v[i]][j][b], newD[j]);
 
	    for(int i = 0; i < C; i++)
	      dist[i] += newD[i], v[i] += (1 << b);
	  }
 
      cout << (dist[b % k] == inf ? -1 : dist[b%k]) << '\n';
    }
  
  
  return 0;
}

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