oj.uz

답안 #985386

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
985386 2024-05-17T17:19:25 Z OAleksa Toll (BOI17_toll) C++14
0 / 100
 78 ms 9812 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 = 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[i] + 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
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 7776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 78 ms 9812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4528 KB Output is correct
6 Incorrect 1 ms 4700 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4528 KB Output is correct
6 Incorrect 1 ms 4700 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 7776 KB Output isn't correct
2 Halted 0 ms 0 KB -