oj.uz

Submission #630894

# Submission time Handle Problem Language Result Execution time Memory
630894 2022-08-17T10:09:17 Z minhcool Toll (BOI17_toll) C++17
100 / 100
 463 ms 226768 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 5e4 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int k, n, m, q;
vector<ii> Adj[N];

int dist[N][555];

int mn_dist[N];

void process(){
	cin >> k >> n >> m >> q;
	for(int i = 1; i <= m; i++){
	    int u, v, w;
	    cin >> u >> v >> w;
	    Adj[v].pb({u, w});
	}
	for(int i = 0; i < n; i++){
	    for(int j = i + 1; j <= min(n - 1, i + 550); j++){
	        dist[i][j - i] = oo;
	        for(auto it : Adj[j]){
	            if(it.fi < i) continue;
	            dist[i][j - i] = min(dist[i][j - i], dist[i][it.fi - i] + it.se);
	        }
	    }
	}
	while(q--){
	    int u, v;
	    cin >> u >> v;
	    int temp1 = u / k, temp2 = v / k;
	    if(temp1 >= temp2){
	        cout << "-1\n";
	        continue;
	    }
	    for(int i = temp1 * k; i < (temp1 + 1) * k; i++) mn_dist[i] = oo;
	    mn_dist[u] = 0;
	    for(; temp1 < (temp2 - 100); temp1 += 100){
	        for(int i = (temp1 + 100) * k; i < (temp1 + 101) * k; i++) mn_dist[i] = oo;
	        for(int i = (temp1 + 100) * k; i < (temp1 + 101) * k; i++){
	            for(int j = temp1 * k; j < (temp1 + 1) * k; j++) mn_dist[i] = min(mn_dist[i], mn_dist[j] + dist[j][i - j]);
	        }
	    }
	    //cout << temp1 << " " << u << " " << v << "\n";
	    //continue;
	    mn_dist[v] = oo;
	    for(int i = temp1 * k; i < (temp1 + 1) * k; i++) mn_dist[v] = min(mn_dist[v], mn_dist[i] + dist[i][v - i]);
	    cout << (mn_dist[v] == oo ? -1 : mn_dist[v]) << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 221228 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 1 ms 1512 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 5 ms 5844 KB Output is correct
6 Correct 5 ms 5872 KB Output is correct
7 Correct 6 ms 5844 KB Output is correct
8 Correct 240 ms 221556 KB Output is correct
9 Correct 242 ms 221576 KB Output is correct
10 Correct 153 ms 219128 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 222064 KB Output is correct
2 Correct 1 ms 1508 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1508 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 19 ms 5980 KB Output is correct
8 Correct 18 ms 6016 KB Output is correct
9 Correct 230 ms 221540 KB Output is correct
10 Correct 383 ms 225368 KB Output is correct
11 Correct 281 ms 223376 KB Output is correct
12 Correct 270 ms 222504 KB Output is correct
13 Correct 289 ms 139100 KB Output is correct
14 Correct 226 ms 136180 KB Output is correct
15 Correct 218 ms 135212 KB Output is correct
16 Correct 216 ms 135244 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1508 KB Output is correct
3 Correct 1 ms 1508 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1508 KB Output is correct
6 Correct 6 ms 5868 KB Output is correct
7 Correct 6 ms 5844 KB Output is correct
8 Correct 9 ms 5972 KB Output is correct
9 Correct 8 ms 5972 KB Output is correct
10 Correct 196 ms 221096 KB Output is correct
11 Correct 267 ms 222008 KB Output is correct
12 Correct 347 ms 223516 KB Output is correct
13 Correct 339 ms 223988 KB Output is correct
14 Correct 323 ms 222668 KB Output is correct
15 Correct 229 ms 134500 KB Output is correct
16 Correct 211 ms 134604 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1508 KB Output is correct
3 Correct 1 ms 1508 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1508 KB Output is correct
6 Correct 6 ms 5868 KB Output is correct
7 Correct 6 ms 5844 KB Output is correct
8 Correct 9 ms 5972 KB Output is correct
9 Correct 8 ms 5972 KB Output is correct
10 Correct 196 ms 221096 KB Output is correct
11 Correct 267 ms 222008 KB Output is correct
12 Correct 347 ms 223516 KB Output is correct
13 Correct 339 ms 223988 KB Output is correct
14 Correct 323 ms 222668 KB Output is correct
15 Correct 229 ms 134500 KB Output is correct
16 Correct 211 ms 134604 KB Output is correct
17 Correct 289 ms 222088 KB Output is correct
18 Correct 1 ms 1492 KB Output is correct
19 Correct 1 ms 1620 KB Output is correct
20 Correct 1 ms 1492 KB Output is correct
21 Correct 1 ms 1492 KB Output is correct
22 Correct 1 ms 1512 KB Output is correct
23 Correct 9 ms 5920 KB Output is correct
24 Correct 10 ms 5872 KB Output is correct
25 Correct 13 ms 6040 KB Output is correct
26 Correct 11 ms 5972 KB Output is correct
27 Correct 220 ms 221484 KB Output is correct
28 Correct 342 ms 225240 KB Output is correct
29 Correct 337 ms 225800 KB Output is correct
30 Correct 333 ms 224116 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 221228 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 1 ms 1512 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 5 ms 5844 KB Output is correct
6 Correct 5 ms 5872 KB Output is correct
7 Correct 6 ms 5844 KB Output is correct
8 Correct 240 ms 221556 KB Output is correct
9 Correct 242 ms 221576 KB Output is correct
10 Correct 153 ms 219128 KB Output is correct
11 Correct 294 ms 222064 KB Output is correct
12 Correct 1 ms 1508 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1508 KB Output is correct
16 Correct 1 ms 1492 KB Output is correct
17 Correct 19 ms 5980 KB Output is correct
18 Correct 18 ms 6016 KB Output is correct
19 Correct 230 ms 221540 KB Output is correct
20 Correct 383 ms 225368 KB Output is correct
21 Correct 281 ms 223376 KB Output is correct
22 Correct 270 ms 222504 KB Output is correct
23 Correct 289 ms 139100 KB Output is correct
24 Correct 226 ms 136180 KB Output is correct
25 Correct 218 ms 135212 KB Output is correct
26 Correct 216 ms 135244 KB Output is correct
27 Correct 1 ms 1492 KB Output is correct
28 Correct 1 ms 1508 KB Output is correct
29 Correct 1 ms 1508 KB Output is correct
30 Correct 1 ms 1492 KB Output is correct
31 Correct 1 ms 1508 KB Output is correct
32 Correct 6 ms 5868 KB Output is correct
33 Correct 6 ms 5844 KB Output is correct
34 Correct 9 ms 5972 KB Output is correct
35 Correct 8 ms 5972 KB Output is correct
36 Correct 196 ms 221096 KB Output is correct
37 Correct 267 ms 222008 KB Output is correct
38 Correct 347 ms 223516 KB Output is correct
39 Correct 339 ms 223988 KB Output is correct
40 Correct 323 ms 222668 KB Output is correct
41 Correct 229 ms 134500 KB Output is correct
42 Correct 211 ms 134604 KB Output is correct
43 Correct 289 ms 222088 KB Output is correct
44 Correct 1 ms 1492 KB Output is correct
45 Correct 1 ms 1620 KB Output is correct
46 Correct 1 ms 1492 KB Output is correct
47 Correct 1 ms 1492 KB Output is correct
48 Correct 1 ms 1512 KB Output is correct
49 Correct 9 ms 5920 KB Output is correct
50 Correct 10 ms 5872 KB Output is correct
51 Correct 13 ms 6040 KB Output is correct
52 Correct 11 ms 5972 KB Output is correct
53 Correct 220 ms 221484 KB Output is correct
54 Correct 342 ms 225240 KB Output is correct
55 Correct 337 ms 225800 KB Output is correct
56 Correct 333 ms 224116 KB Output is correct
57 Correct 463 ms 226768 KB Output is correct
58 Correct 234 ms 221516 KB Output is correct
59 Correct 296 ms 223596 KB Output is correct