oj.uz

Submission #396418

# Submission time Handle Problem Language Result Execution time Memory
396418 2021-04-30T00:05:24 Z ChrisT Escape Route (JOI21_escape_route) C++17
35 / 100
 9000 ms 150160 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%s <= 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++) {
				for (int j = 1; j <= n; j++) if (adj[i][j] < 1e18 && pre[st][id][i] < 1e18 && pre[st][id][j] < 1e18) {
					long long md = pre[st][id][i]%s;
					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++) {
			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 30 ms 64956 KB Output is correct
2 Correct 74 ms 64972 KB Output is correct
3 Correct 1333 ms 64972 KB Output is correct
4 Correct 27 ms 65008 KB Output is correct
5 Correct 30 ms 65020 KB Output is correct
6 Correct 28 ms 65016 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2479 ms 131916 KB Output is correct
2 Correct 2531 ms 148380 KB Output is correct
3 Correct 2635 ms 138424 KB Output is correct
4 Correct 2693 ms 149684 KB Output is correct
5 Correct 2686 ms 149288 KB Output is correct
6 Correct 29 ms 64964 KB Output is correct
7 Correct 2607 ms 137468 KB Output is correct
8 Correct 1336 ms 134188 KB Output is correct
9 Correct 2658 ms 127648 KB Output is correct
10 Correct 2653 ms 148992 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64956 KB Output is correct
2 Correct 74 ms 64972 KB Output is correct
3 Correct 1333 ms 64972 KB Output is correct
4 Correct 27 ms 65008 KB Output is correct
5 Correct 30 ms 65020 KB Output is correct
6 Correct 28 ms 65016 KB Output is correct
7 Correct 2479 ms 131916 KB Output is correct
8 Correct 2531 ms 148380 KB Output is correct
9 Correct 2635 ms 138424 KB Output is correct
10 Correct 2693 ms 149684 KB Output is correct
11 Correct 2686 ms 149288 KB Output is correct
12 Correct 29 ms 64964 KB Output is correct
13 Correct 2607 ms 137468 KB Output is correct
14 Correct 1336 ms 134188 KB Output is correct
15 Correct 2658 ms 127648 KB Output is correct
16 Correct 2653 ms 148992 KB Output is correct
17 Correct 3077 ms 136404 KB Output is correct
18 Correct 2868 ms 132288 KB Output is correct
19 Correct 2636 ms 149248 KB Output is correct
20 Correct 2933 ms 137520 KB Output is correct
21 Correct 3058 ms 150160 KB Output is correct
22 Correct 3069 ms 149892 KB Output is correct
23 Correct 2994 ms 137104 KB Output is correct
24 Correct 1379 ms 134044 KB Output is correct
25 Correct 3045 ms 126868 KB Output is correct
26 Correct 3098 ms 149848 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64956 KB Output is correct
2 Correct 74 ms 64972 KB Output is correct
3 Correct 1333 ms 64972 KB Output is correct
4 Correct 27 ms 65008 KB Output is correct
5 Correct 30 ms 65020 KB Output is correct
6 Correct 28 ms 65016 KB Output is correct
7 Correct 2479 ms 131916 KB Output is correct
8 Correct 2531 ms 148380 KB Output is correct
9 Correct 2635 ms 138424 KB Output is correct
10 Correct 2693 ms 149684 KB Output is correct
11 Correct 2686 ms 149288 KB Output is correct
12 Correct 29 ms 64964 KB Output is correct
13 Correct 2607 ms 137468 KB Output is correct
14 Correct 1336 ms 134188 KB Output is correct
15 Correct 2658 ms 127648 KB Output is correct
16 Correct 2653 ms 148992 KB Output is correct
17 Correct 3077 ms 136404 KB Output is correct
18 Correct 2868 ms 132288 KB Output is correct
19 Correct 2636 ms 149248 KB Output is correct
20 Correct 2933 ms 137520 KB Output is correct
21 Correct 3058 ms 150160 KB Output is correct
22 Correct 3069 ms 149892 KB Output is correct
23 Correct 2994 ms 137104 KB Output is correct
24 Correct 1379 ms 134044 KB Output is correct
25 Correct 3045 ms 126868 KB Output is correct
26 Correct 3098 ms 149848 KB Output is correct
27 Execution timed out 9026 ms 123220 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64956 KB Output is correct
2 Correct 74 ms 64972 KB Output is correct
3 Correct 1333 ms 64972 KB Output is correct
4 Correct 27 ms 65008 KB Output is correct
5 Correct 30 ms 65020 KB Output is correct
6 Correct 28 ms 65016 KB Output is correct
7 Correct 2479 ms 131916 KB Output is correct
8 Correct 2531 ms 148380 KB Output is correct
9 Correct 2635 ms 138424 KB Output is correct
10 Correct 2693 ms 149684 KB Output is correct
11 Correct 2686 ms 149288 KB Output is correct
12 Correct 29 ms 64964 KB Output is correct
13 Correct 2607 ms 137468 KB Output is correct
14 Correct 1336 ms 134188 KB Output is correct
15 Correct 2658 ms 127648 KB Output is correct
16 Correct 2653 ms 148992 KB Output is correct
17 Correct 3077 ms 136404 KB Output is correct
18 Correct 2868 ms 132288 KB Output is correct
19 Correct 2636 ms 149248 KB Output is correct
20 Correct 2933 ms 137520 KB Output is correct
21 Correct 3058 ms 150160 KB Output is correct
22 Correct 3069 ms 149892 KB Output is correct
23 Correct 2994 ms 137104 KB Output is correct
24 Correct 1379 ms 134044 KB Output is correct
25 Correct 3045 ms 126868 KB Output is correct
26 Correct 3098 ms 149848 KB Output is correct
27 Execution timed out 9026 ms 123220 KB Time limit exceeded
28 Halted 0 ms 0 KB -