oj.uz

Submission #396457

# Submission time Handle Problem Language Result Execution time Memory
396457 2021-04-30T01:36:01 Z ChrisT Escape Route (JOI21_escape_route) C++17
70 / 100
 8868 ms 281472 KB 
#include <bits/stdc++.h>
using namespace std;
const int MN = 60 + 1;
long long pre[MN][MN*MN][MN], stop[MN][MN];
vector<long long> times[MN];
long long adj[MN][MN], bad[MN][MN];
bool vis[MN];
vector<long long> calculate_necessary_time (int n, int m, long long s, int q, vector<int> a, vector<int> b, vector<long long> l, vector<long long> c, vector<int> u, vector<int> v, vector<long long> T) {
	memset(adj,0x3f,sizeof adj);
	for (int i = 0; i < m; i++) {
		adj[++a[i]][++b[i]] = l[i];
		adj[b[i]][a[i]] = l[i];
		bad[a[i]][b[i]] = bad[b[i]][a[i]] = c[i];
	}
	for (int st = 1; st <= n; st++) {
		memset(stop[st],0x3f,sizeof stop[st]); memset(vis,0,sizeof vis);
		stop[st][st] = 0;
		for (int iter = 0; iter < n; iter++) {
			int mn = -1;
			for (int i = 1; i <= n; i++) if (!vis[i] && (mn == -1 || stop[st][i] < stop[st][mn])) mn = i;
			if (mn == -1 || stop[st][mn] > 1e18) break;
			vis[mn] = true;
			for (int i = 1; i <= n; i++) if (adj[mn][i] < 1e18) {
				long long att = stop[st][mn];
				if (att%s <= bad[mn][i] - adj[mn][i]) att += adj[mn][i];
				else att += (s - att%s) + adj[mn][i];
				stop[st][i] = min(stop[st][i],att);
			}
		}
	}
	for (int st = 1; st <= n; st++) { //no stop all go
		times[st].push_back(0);
		for (int id = 0; id < (int)times[st].size(); id++) {
			long long t = times[st][id];
			memset(pre[st][id],0x3f,sizeof pre[st][id]);
			memset(vis,0,sizeof vis);
			pre[st][id][st] = t;
			for (int iter = 0; iter < n; iter++) {
				int mn = -1;
				for (int i = 1; i <= n; i++) if (!vis[i] && (mn == -1 || pre[st][id][i] < pre[st][id][mn])) mn = i;
				if (mn == -1 || pre[st][id][mn] > 1e18) break;
				vis[mn] = true;
				for (int i = 1; i <= n; i++) if (adj[mn][i] < 1e18) {
					long long att = pre[st][id][mn];
					if (att <= bad[mn][i] - adj[mn][i]) att += adj[mn][i];
					else continue; //no stop
					pre[st][id][i] = min(pre[st][id][i],att);
				}
			}
			long long nextTime = 1e18 + 5;
			for (int i = 1; i <= n; i++) if (pre[st][id][i] < 1e18) {
				long long md = pre[st][id][i];
				for (int j = 1; j <= n; j++) if (md <= bad[i][j] - adj[i][j]) {
					nextTime = min(nextTime,bad[i][j] - adj[i][j] + 1 - md + t);
				}
			}
			if (nextTime < s) times[st].push_back(nextTime);
		}
	}
	vector<long long> ret(q);
	for (int i = 0; i < q; i++) {
		++u[i]; ++v[i];
		int id = upper_bound(times[u[i]].begin(),times[u[i]].end(),T[i]) - times[u[i]].begin() - 1;
		long long t = times[u[i]][id];
		ret[i] = pre[u[i]][id][v[i]] - t;
		for (int ed = 1; ed <= n; ed++) if (pre[u[i]][id][ed] < 1e18) {
			long long att = pre[u[i]][id][ed] + T[i] - t;
			if (att > s) att = 2 * s;
          	else if (att > 0) att = s;
			ret[i] = min(ret[i],att+stop[ed][v[i]]-T[i]);
		}
	}
	return ret;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64972 KB Output is correct
2 Correct 70 ms 64984 KB Output is correct
3 Correct 793 ms 64992 KB Output is correct
4 Correct 28 ms 64960 KB Output is correct
5 Correct 30 ms 65008 KB Output is correct
6 Correct 32 ms 65012 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1842 ms 131916 KB Output is correct
2 Correct 1730 ms 148456 KB Output is correct
3 Correct 1703 ms 138484 KB Output is correct
4 Correct 1910 ms 149880 KB Output is correct
5 Correct 1886 ms 149268 KB Output is correct
6 Correct 31 ms 64972 KB Output is correct
7 Correct 1712 ms 137320 KB Output is correct
8 Correct 587 ms 134140 KB Output is correct
9 Correct 1782 ms 127560 KB Output is correct
10 Correct 1858 ms 149040 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64972 KB Output is correct
2 Correct 70 ms 64984 KB Output is correct
3 Correct 793 ms 64992 KB Output is correct
4 Correct 28 ms 64960 KB Output is correct
5 Correct 30 ms 65008 KB Output is correct
6 Correct 32 ms 65012 KB Output is correct
7 Correct 1842 ms 131916 KB Output is correct
8 Correct 1730 ms 148456 KB Output is correct
9 Correct 1703 ms 138484 KB Output is correct
10 Correct 1910 ms 149880 KB Output is correct
11 Correct 1886 ms 149268 KB Output is correct
12 Correct 31 ms 64972 KB Output is correct
13 Correct 1712 ms 137320 KB Output is correct
14 Correct 587 ms 134140 KB Output is correct
15 Correct 1782 ms 127560 KB Output is correct
16 Correct 1858 ms 149040 KB Output is correct
17 Correct 2439 ms 136232 KB Output is correct
18 Correct 2212 ms 131976 KB Output is correct
19 Correct 1915 ms 149176 KB Output is correct
20 Correct 2163 ms 137492 KB Output is correct
21 Correct 2540 ms 149980 KB Output is correct
22 Correct 2328 ms 149864 KB Output is correct
23 Correct 2189 ms 137016 KB Output is correct
24 Correct 683 ms 134056 KB Output is correct
25 Correct 2363 ms 126832 KB Output is correct
26 Correct 2318 ms 149832 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64972 KB Output is correct
2 Correct 70 ms 64984 KB Output is correct
3 Correct 793 ms 64992 KB Output is correct
4 Correct 28 ms 64960 KB Output is correct
5 Correct 30 ms 65008 KB Output is correct
6 Correct 32 ms 65012 KB Output is correct
7 Correct 1842 ms 131916 KB Output is correct
8 Correct 1730 ms 148456 KB Output is correct
9 Correct 1703 ms 138484 KB Output is correct
10 Correct 1910 ms 149880 KB Output is correct
11 Correct 1886 ms 149268 KB Output is correct
12 Correct 31 ms 64972 KB Output is correct
13 Correct 1712 ms 137320 KB Output is correct
14 Correct 587 ms 134140 KB Output is correct
15 Correct 1782 ms 127560 KB Output is correct
16 Correct 1858 ms 149040 KB Output is correct
17 Correct 2439 ms 136232 KB Output is correct
18 Correct 2212 ms 131976 KB Output is correct
19 Correct 1915 ms 149176 KB Output is correct
20 Correct 2163 ms 137492 KB Output is correct
21 Correct 2540 ms 149980 KB Output is correct
22 Correct 2328 ms 149864 KB Output is correct
23 Correct 2189 ms 137016 KB Output is correct
24 Correct 683 ms 134056 KB Output is correct
25 Correct 2363 ms 126832 KB Output is correct
26 Correct 2318 ms 149832 KB Output is correct
27 Correct 8868 ms 206916 KB Output is correct
28 Correct 7768 ms 236068 KB Output is correct
29 Correct 7959 ms 270952 KB Output is correct
30 Correct 8087 ms 247464 KB Output is correct
31 Correct 8511 ms 280440 KB Output is correct
32 Correct 8562 ms 280960 KB Output is correct
33 Correct 769 ms 197688 KB Output is correct
34 Correct 8722 ms 242980 KB Output is correct
35 Correct 8516 ms 281472 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64972 KB Output is correct
2 Correct 70 ms 64984 KB Output is correct
3 Correct 793 ms 64992 KB Output is correct
4 Correct 28 ms 64960 KB Output is correct
5 Correct 30 ms 65008 KB Output is correct
6 Correct 32 ms 65012 KB Output is correct
7 Correct 1842 ms 131916 KB Output is correct
8 Correct 1730 ms 148456 KB Output is correct
9 Correct 1703 ms 138484 KB Output is correct
10 Correct 1910 ms 149880 KB Output is correct
11 Correct 1886 ms 149268 KB Output is correct
12 Correct 31 ms 64972 KB Output is correct
13 Correct 1712 ms 137320 KB Output is correct
14 Correct 587 ms 134140 KB Output is correct
15 Correct 1782 ms 127560 KB Output is correct
16 Correct 1858 ms 149040 KB Output is correct
17 Correct 2439 ms 136232 KB Output is correct
18 Correct 2212 ms 131976 KB Output is correct
19 Correct 1915 ms 149176 KB Output is correct
20 Correct 2163 ms 137492 KB Output is correct
21 Correct 2540 ms 149980 KB Output is correct
22 Correct 2328 ms 149864 KB Output is correct
23 Correct 2189 ms 137016 KB Output is correct
24 Correct 683 ms 134056 KB Output is correct
25 Correct 2363 ms 126832 KB Output is correct
26 Correct 2318 ms 149832 KB Output is correct
27 Correct 8868 ms 206916 KB Output is correct
28 Correct 7768 ms 236068 KB Output is correct
29 Correct 7959 ms 270952 KB Output is correct
30 Correct 8087 ms 247464 KB Output is correct
31 Correct 8511 ms 280440 KB Output is correct
32 Correct 8562 ms 280960 KB Output is correct
33 Correct 769 ms 197688 KB Output is correct
34 Correct 8722 ms 242980 KB Output is correct
35 Correct 8516 ms 281472 KB Output is correct
36 Runtime error 202 ms 158016 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -