oj.uz

Submission #985381

# Submission time Handle Problem Language Result Execution time Memory
985381 2024-05-17T17:11:48 Z OAleksa Toll (BOI17_toll) C++14
0 / 100
 3000 ms 9564 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 8032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3045 ms 9564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 8032 KB Time limit exceeded
2 Halted 0 ms 0 KB -