oj.uz

Submission #524354

# Submission time Handle Problem Language Result Execution time Memory
524354 2022-02-09T05:36:19 Z amunduzbaev Escape Route (JOI21_escape_route) C++17
100 / 100
 2540 ms 200404 KB 
#include "escape_route.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define int long long
#define i32 int32_t

const int INF = 1e18;
const int NN = 91;
int d[NN][NN], g[NN][NN];
int de[NN][NN][NN], used[NN];
vector<int> p[NN];

vector<int> calculate_necessary_time(
i32 n, i32 m, int S, i32 q, vector<i32> a, vector<i32> b,
vector<int> l, vector<int> c, vector<i32> u,
vector<i32> v, vector<int> T) {
	memset(g, -1, sizeof g);
	for(int i=0;i<m;i++){
		g[a[i]][b[i]] = 
		g[b[i]][a[i]] = i;
		p[a[i]].push_back(i);
		p[b[i]].push_back(i);
	}
	
	auto go = [&](int i, int* d){
		memset(used, 0, sizeof used);
		while(~i){
			used[i] = 1;
			int t=-1;
			for(int j=0;j<n;j++){
				if(used[j]) continue;
				if(~g[i][j]){
					int k=g[i][j];
					if(d[i]%S + l[k] <= c[k]){
						d[j] = min(d[j], d[i] + l[k]);
					} else {
						d[j] = min(d[j], d[i] + (S - d[i]%S) + l[k]);
					}
				}
				
				if(d[j] < INF && (t == -1 || d[j] < d[t])) t = j;
			}
			
			i = t;
		}
	};
	//~ cout<<d[0][0]<<"\n"<<INF<<"\n";
	for(int i=0;i<NN;i++){
		for(int j=0;j<NN;j++){
			for(int k=0;k<NN;k++){
				de[i][j][k] = INF;
			} d[i][j] = INF;
		}
	}
	
	for(int i=0;i<n;i++){
		d[i][i] = 0;
		go(i, d[i]);
		
		sort(p[i].begin(), p[i].end(), [&](int i, int j){
			return c[i] - l[i] > c[j] - l[j];
		});
		for(int j=0;j<(int)p[i].size();j++){
			de[j][i][i] = c[p[i][j]] - l[p[i][j]];
			go(i, de[j][i]);
			for(int k=0;k<n;k++){
				if(de[j][i][k] >= S) de[j][i][k] = INF;
				else de[j][i][k] -= (c[p[i][j]] - l[p[i][j]]);
			}
		}
	}
	
	vector<vector<int>> qq(n);
	vector<int> res(q);
	for(int i=0;i<q;i++){
		qq[u[i]].push_back(i);
		res[i] = INF;
	}
	
	for(int i=0;i<n;i++){
		sort(qq[i].begin(), qq[i].end(), [&](int i, int j){
			return (T[i] < T[j]);
		});
		
		vector<int> cnt(n), D(n, INF), cur(n, -1);
		D[i] = 0;
		if(!p[i].empty()) cur[i] = c[p[i][0]] - l[p[i][0]];
		while(!qq[i].empty()){
			int j = max_element(cur.begin(), cur.end()) - cur.begin();
			while(!qq[i].empty() && T[qq[i].back()] > cur[j]){
				int in = qq[i].back(); qq[i].pop_back();
				for(int g=0;g<n;g++){
					if(D[g] == INF) continue;
					res[in] = min(res[in], D[g] + 
					(g != v[in] ? (S - D[g] - T[in]) : 0ll) + d[g][v[in]]);
				}
			}
			
			if(cur[j] < 0) break;
			for(int g=0;g<n;g++){
				if(D[g] > D[j] + de[cnt[j]][j][g]){
					D[g] = D[j] + de[cnt[j]][j][g];
					if(cnt[g] < (int)p[g].size()){
						cur[g] = c[p[g][cnt[g]]] - l[p[g][cnt[g]]] - D[g];
					}
				}
			}
			
			cnt[j]++;
			if(cnt[j] < (int)p[j].size()){
				cur[j] = c[p[j][cnt[j]]] - l[p[j][cnt[j]]] - D[j];
			} else {
				cur[j] = -1;
			}
		}
		
		//~ cout<<"here"<<endl;
	} return res;
}

/*

4 5 20 1
0 1 3 19
0 2 2 8
1 2 4 15
1 3 5 14
2 3 1 18
0 3 7

4 5 20 6
0 1 3 19
0 2 2 8
1 2 4 15
1 3 5 14
2 3 1 18
0 3 5
0 3 7
0 3 9
2 0 6
3 1 10
1 2 15

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64972 KB Output is correct
2 Correct 31 ms 64992 KB Output is correct
3 Correct 53 ms 65092 KB Output is correct
4 Correct 32 ms 65036 KB Output is correct
5 Correct 33 ms 64956 KB Output is correct
6 Correct 27 ms 64956 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1564 ms 112156 KB Output is correct
2 Correct 1571 ms 126224 KB Output is correct
3 Correct 1464 ms 117944 KB Output is correct
4 Correct 1626 ms 127336 KB Output is correct
5 Correct 1607 ms 127392 KB Output is correct
6 Correct 28 ms 64972 KB Output is correct
7 Correct 1486 ms 158812 KB Output is correct
8 Correct 1374 ms 200404 KB Output is correct
9 Correct 1488 ms 154872 KB Output is correct
10 Correct 1588 ms 187416 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64972 KB Output is correct
2 Correct 31 ms 64992 KB Output is correct
3 Correct 53 ms 65092 KB Output is correct
4 Correct 32 ms 65036 KB Output is correct
5 Correct 33 ms 64956 KB Output is correct
6 Correct 27 ms 64956 KB Output is correct
7 Correct 1564 ms 112156 KB Output is correct
8 Correct 1571 ms 126224 KB Output is correct
9 Correct 1464 ms 117944 KB Output is correct
10 Correct 1626 ms 127336 KB Output is correct
11 Correct 1607 ms 127392 KB Output is correct
12 Correct 28 ms 64972 KB Output is correct
13 Correct 1486 ms 158812 KB Output is correct
14 Correct 1374 ms 200404 KB Output is correct
15 Correct 1488 ms 154872 KB Output is correct
16 Correct 1588 ms 187416 KB Output is correct
17 Correct 1417 ms 158636 KB Output is correct
18 Correct 1460 ms 158740 KB Output is correct
19 Correct 1522 ms 182176 KB Output is correct
20 Correct 1415 ms 162516 KB Output is correct
21 Correct 1530 ms 191664 KB Output is correct
22 Correct 1550 ms 185672 KB Output is correct
23 Correct 1447 ms 159200 KB Output is correct
24 Correct 1427 ms 196832 KB Output is correct
25 Correct 1471 ms 155932 KB Output is correct
26 Correct 1545 ms 185080 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64972 KB Output is correct
2 Correct 31 ms 64992 KB Output is correct
3 Correct 53 ms 65092 KB Output is correct
4 Correct 32 ms 65036 KB Output is correct
5 Correct 33 ms 64956 KB Output is correct
6 Correct 27 ms 64956 KB Output is correct
7 Correct 1564 ms 112156 KB Output is correct
8 Correct 1571 ms 126224 KB Output is correct
9 Correct 1464 ms 117944 KB Output is correct
10 Correct 1626 ms 127336 KB Output is correct
11 Correct 1607 ms 127392 KB Output is correct
12 Correct 28 ms 64972 KB Output is correct
13 Correct 1486 ms 158812 KB Output is correct
14 Correct 1374 ms 200404 KB Output is correct
15 Correct 1488 ms 154872 KB Output is correct
16 Correct 1588 ms 187416 KB Output is correct
17 Correct 1417 ms 158636 KB Output is correct
18 Correct 1460 ms 158740 KB Output is correct
19 Correct 1522 ms 182176 KB Output is correct
20 Correct 1415 ms 162516 KB Output is correct
21 Correct 1530 ms 191664 KB Output is correct
22 Correct 1550 ms 185672 KB Output is correct
23 Correct 1447 ms 159200 KB Output is correct
24 Correct 1427 ms 196832 KB Output is correct
25 Correct 1471 ms 155932 KB Output is correct
26 Correct 1545 ms 185080 KB Output is correct
27 Correct 1765 ms 156892 KB Output is correct
28 Correct 1761 ms 155636 KB Output is correct
29 Correct 1838 ms 176412 KB Output is correct
30 Correct 1701 ms 159636 KB Output is correct
31 Correct 1815 ms 184704 KB Output is correct
32 Correct 1812 ms 170576 KB Output is correct
33 Correct 1486 ms 181488 KB Output is correct
34 Correct 1723 ms 155404 KB Output is correct
35 Correct 1795 ms 168300 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64972 KB Output is correct
2 Correct 31 ms 64992 KB Output is correct
3 Correct 53 ms 65092 KB Output is correct
4 Correct 32 ms 65036 KB Output is correct
5 Correct 33 ms 64956 KB Output is correct
6 Correct 27 ms 64956 KB Output is correct
7 Correct 1564 ms 112156 KB Output is correct
8 Correct 1571 ms 126224 KB Output is correct
9 Correct 1464 ms 117944 KB Output is correct
10 Correct 1626 ms 127336 KB Output is correct
11 Correct 1607 ms 127392 KB Output is correct
12 Correct 28 ms 64972 KB Output is correct
13 Correct 1486 ms 158812 KB Output is correct
14 Correct 1374 ms 200404 KB Output is correct
15 Correct 1488 ms 154872 KB Output is correct
16 Correct 1588 ms 187416 KB Output is correct
17 Correct 1417 ms 158636 KB Output is correct
18 Correct 1460 ms 158740 KB Output is correct
19 Correct 1522 ms 182176 KB Output is correct
20 Correct 1415 ms 162516 KB Output is correct
21 Correct 1530 ms 191664 KB Output is correct
22 Correct 1550 ms 185672 KB Output is correct
23 Correct 1447 ms 159200 KB Output is correct
24 Correct 1427 ms 196832 KB Output is correct
25 Correct 1471 ms 155932 KB Output is correct
26 Correct 1545 ms 185080 KB Output is correct
27 Correct 1765 ms 156892 KB Output is correct
28 Correct 1761 ms 155636 KB Output is correct
29 Correct 1838 ms 176412 KB Output is correct
30 Correct 1701 ms 159636 KB Output is correct
31 Correct 1815 ms 184704 KB Output is correct
32 Correct 1812 ms 170576 KB Output is correct
33 Correct 1486 ms 181488 KB Output is correct
34 Correct 1723 ms 155404 KB Output is correct
35 Correct 1795 ms 168300 KB Output is correct
36 Correct 2513 ms 157216 KB Output is correct
37 Correct 2484 ms 155724 KB Output is correct
38 Correct 2346 ms 159720 KB Output is correct
39 Correct 2506 ms 186780 KB Output is correct
40 Correct 2540 ms 188060 KB Output is correct
41 Correct 1579 ms 198380 KB Output is correct
42 Correct 2460 ms 157136 KB Output is correct
43 Correct 2459 ms 155996 KB Output is correct