Submission #985345

#	Time	Username	Problem	Language	Result	Execution time	Memory
985345		OAleksa	Toll (BOI17_toll)	C++14	0 / 100	67 ms	8276 KiB

toll

#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N = 5e4 + 69;
int n, m, k, q, dis[N][6], d[N];
vector<pair<int, int>> g[N];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> k >> n >> m >> q;
  	const int B = 100 * k;
  	for (int i = 0;i < n;i++) {
  		for (int j = 0;j < k;j++)
  			dis[i][j] = 1e16;
  	}
  	for (int i = 1;i <= m;i++) {
  		int a, b, c;
  		cin >> a >> b >> c;
  		g[a].push_back({b, c});
  	}
  	for (int i = 0;i < n;i++) {
  		int x = i / B;
  		int en = (i / B + 1) * B;
  		d[i] = 0;
  		for (int j = i + 1;j < min(n, en);j++)
  			d[j] = 1e18;
  		for (int j = i;j < min(n, en);j++) {
  			for (auto u : g[j]) {
  				d[u.f] = min(d[u.f], d[i] + u.s);
  			}
  		}
  		for (int j = en - 1;j >= max(i, en - k);j--)
  			dis[i][j % k] = d[j];
  	}
  	while (q--) {
  		int a, b;
  		cin >> a >> b;
  		if (a / B == b / B) {
  			for (int j = a;j <= b;j++)
  				d[j] = 1e18;
  			d[a] = 0;
  			for (int i = a;i < b;i++) {
  				for (auto u : g[i])
  					d[u.f] = min(d[u.f], d[i] + u.s);
  			}
  			if (d[b] >= 1e18)
  				cout << "-1\n";
  			else
  				cout << d[b] << '\n';
  		}
  		else {
  			int en = (a / B + 1) * B;
  			for (int j = en - 1;j >= en - k;j--)
  				d[j] = dis[a][j % k];
  			a = en - 1;
  			while (a / B != b / B) {
  				en = a + 1;
  				for (int j = en;j < en + k;j++)
  					d[j] = 1e18;
  				for (int j = en - 1;j >= en - k;j--) {
  					for (auto u : g[j])
  						d[u.f] = min(d[u.f], d[j] + u.s);
  				}
  				int ee = (en / B + 1) * B;
  				for (int j = ee - 1;j >= ee - k;j--)
  					d[j] = 1e18;
  				for (int j = en;j < en + k;j++) {
  					for (int i = 0;i < k;i++) {
  						int o = k - i;
  						d[ee - o] = min(d[ee - o], dis[j][i]);
  					}
  				}
  				a = ee - 1;
  			}
  			for (int i = en;i <= b;i++) {
  				for (auto u : g[i])
  					d[u.f] = min(d[u.f], d[i] + u.s);
  			}
  			if (d[b] >= 1e18)
  				cout << "-1\n";
  			else
  				cout << d[b] << '\n';
  		}
  	}
  }
  return 0; 
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:28:9: warning: unused variable 'x' [-Wunused-variable]
   28 |     int x = i / B;
      |         ^

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