Submission #985381

#	Time	Username	Problem	Language	Result	Execution time	Memory
985381		OAleksa	Toll (BOI17_toll)	C++14	0 / 100	3050 ms	9564 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 = 1 * 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;
  		int x = min(n, en + k);
  		for (int j = i + 1;j < x;j++)
  			d[j] = inf;
  		for (int j = i;j < x;j++) {
  			for (auto u : g[j]) {
  				d[u.f] = min(d[u.f], d[i] + u.s);
  			}
  		}
  		--x;
  		while (x % k != 0) {
  			dd[i].push_back({x, d[x]});
  			--x;
  		}
  		dd[i].push_back({x, d[x]});
  	}
  	while (q--) {
  		int a, b;
  		cin >> a >> b;
  		set<int> st;
  		st.insert(a);
  		d[a] = 0;
  		int x = (b / B) * B;
  		for (int j = x;j <= b;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;
  			while (!st.empty()) {
  				auto v = *st.begin();
					if (v / B == en / B)
						break;
					st.erase(v);
  				for (auto u : dd[v]) {
  					d[u.f] = min(d[u.f], d[v] + u.s);
  					st.insert(u.f);
  				}
  			}
  			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: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44