Submission #985388

#	Time	Username	Problem	Language	Result	Execution time	Memory
985388		OAleksa	Toll (BOI17_toll)	C++14	100 / 100	158 ms	16212 KiB

toll

#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N = 5e4 + 69;
const int inf = 1e12;
int n, m, k, q, dis[N][6], d[N];
vector<pair<int, int>> g[N];
vector<pair<int, int>> dd[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 = 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 en = (i / B + 1) * B;
  		d[i] = 0;
  		for (int j = i + 1;j < en + k;j++)
  			d[j] = inf;
  		for (int j = i;j < en + k;j++) {
  			for (auto u : g[j]) {
  				d[u.f] = min(d[u.f], d[j] + u.s);
  			}
  		}
  		for (int j = en + k - 1;j >= en;j--)
  			dd[i].push_back({j, d[j]});
  	}
  	while (q--) {
  		int a, b;
  		cin >> a >> b;
  		int x = (b / B) * B;
  		for (int j = x;j <= b;j++)
  			d[j] = inf;
  		for (int j = a;j < a + k;j++)
  			d[j] = inf;
  		d[a] = 0;
  		while (a / B != b / B) {	
  			int en = (a / B + 1) * B;
  			for (int j = en;j < en + k;j++)
  				d[j] = inf;
  			for (int j = a;j < a + k;j++) {
  				for (auto u : dd[j])
  					d[u.f] = inf;
  			}
  			for (int j = a;j < a + k;j++) {
  				for (auto u : dd[j])
  					d[u.f] = min(d[u.f], d[j] + u.s);
  			}
  			a = en;
  		}
			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] >= inf)
				cout << "-1\n";
			else
				cout << d[b] << '\n';
		}
  }
  return 0; 
}

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