oj.uz

Submission #396452

# Submission time Handle Problem Language Result Execution time Memory
396452 2021-04-30T01:19:42 Z ChrisT Escape Route (JOI21_escape_route) C++17
35 / 100
 9000 ms 171080 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++) {
				long long md = pre[st][id][i];
				for (int j = 1; j <= n; j++) if (pre[st][id][i] < 1e18 && 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++) {
			long long att = pre[u[i]][id][ed] + T[i] - t;
			att = (att + s - 1) / s * 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 62 ms 65036 KB Output is correct
3 Correct 855 ms 64960 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 31 ms 64980 KB Output is correct
6 Correct 30 ms 64992 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2017 ms 131984 KB Output is correct
2 Correct 1998 ms 148432 KB Output is correct
3 Correct 2125 ms 138468 KB Output is correct
4 Correct 2148 ms 149772 KB Output is correct
5 Correct 2223 ms 149324 KB Output is correct
6 Correct 30 ms 64936 KB Output is correct
7 Correct 2208 ms 137348 KB Output is correct
8 Correct 1335 ms 134180 KB Output is correct
9 Correct 2163 ms 127560 KB Output is correct
10 Correct 2148 ms 149160 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 62 ms 65036 KB Output is correct
3 Correct 855 ms 64960 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 31 ms 64980 KB Output is correct
6 Correct 30 ms 64992 KB Output is correct
7 Correct 2017 ms 131984 KB Output is correct
8 Correct 1998 ms 148432 KB Output is correct
9 Correct 2125 ms 138468 KB Output is correct
10 Correct 2148 ms 149772 KB Output is correct
11 Correct 2223 ms 149324 KB Output is correct
12 Correct 30 ms 64936 KB Output is correct
13 Correct 2208 ms 137348 KB Output is correct
14 Correct 1335 ms 134180 KB Output is correct
15 Correct 2163 ms 127560 KB Output is correct
16 Correct 2148 ms 149160 KB Output is correct
17 Correct 2569 ms 136244 KB Output is correct
18 Correct 2403 ms 132048 KB Output is correct
19 Correct 2119 ms 149184 KB Output is correct
20 Correct 2464 ms 137460 KB Output is correct
21 Correct 2541 ms 150144 KB Output is correct
22 Correct 2561 ms 149952 KB Output is correct
23 Correct 2522 ms 137072 KB Output is correct
24 Correct 1448 ms 134076 KB Output is correct
25 Correct 2513 ms 126872 KB Output is correct
26 Correct 2571 ms 149916 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64972 KB Output is correct
2 Correct 62 ms 65036 KB Output is correct
3 Correct 855 ms 64960 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 31 ms 64980 KB Output is correct
6 Correct 30 ms 64992 KB Output is correct
7 Correct 2017 ms 131984 KB Output is correct
8 Correct 1998 ms 148432 KB Output is correct
9 Correct 2125 ms 138468 KB Output is correct
10 Correct 2148 ms 149772 KB Output is correct
11 Correct 2223 ms 149324 KB Output is correct
12 Correct 30 ms 64936 KB Output is correct
13 Correct 2208 ms 137348 KB Output is correct
14 Correct 1335 ms 134180 KB Output is correct
15 Correct 2163 ms 127560 KB Output is correct
16 Correct 2148 ms 149160 KB Output is correct
17 Correct 2569 ms 136244 KB Output is correct
18 Correct 2403 ms 132048 KB Output is correct
19 Correct 2119 ms 149184 KB Output is correct
20 Correct 2464 ms 137460 KB Output is correct
21 Correct 2541 ms 150144 KB Output is correct
22 Correct 2561 ms 149952 KB Output is correct
23 Correct 2522 ms 137072 KB Output is correct
24 Correct 1448 ms 134076 KB Output is correct
25 Correct 2513 ms 126872 KB Output is correct
26 Correct 2571 ms 149916 KB Output is correct
27 Execution timed out 9100 ms 171080 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64972 KB Output is correct
2 Correct 62 ms 65036 KB Output is correct
3 Correct 855 ms 64960 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 31 ms 64980 KB Output is correct
6 Correct 30 ms 64992 KB Output is correct
7 Correct 2017 ms 131984 KB Output is correct
8 Correct 1998 ms 148432 KB Output is correct
9 Correct 2125 ms 138468 KB Output is correct
10 Correct 2148 ms 149772 KB Output is correct
11 Correct 2223 ms 149324 KB Output is correct
12 Correct 30 ms 64936 KB Output is correct
13 Correct 2208 ms 137348 KB Output is correct
14 Correct 1335 ms 134180 KB Output is correct
15 Correct 2163 ms 127560 KB Output is correct
16 Correct 2148 ms 149160 KB Output is correct
17 Correct 2569 ms 136244 KB Output is correct
18 Correct 2403 ms 132048 KB Output is correct
19 Correct 2119 ms 149184 KB Output is correct
20 Correct 2464 ms 137460 KB Output is correct
21 Correct 2541 ms 150144 KB Output is correct
22 Correct 2561 ms 149952 KB Output is correct
23 Correct 2522 ms 137072 KB Output is correct
24 Correct 1448 ms 134076 KB Output is correct
25 Correct 2513 ms 126872 KB Output is correct
26 Correct 2571 ms 149916 KB Output is correct
27 Execution timed out 9100 ms 171080 KB Time limit exceeded
28 Halted 0 ms 0 KB -