oj.uz

Submission #393873

# Submission time Handle Problem Language Result Execution time Memory
393873 2021-04-24T18:03:57 Z keko37 Escape Route (JOI21_escape_route) C++17
100 / 100
 6382 ms 698844 KB 
#include<bits/stdc++.h>
#include "escape_route.h"

using namespace std;

typedef long long llint;
typedef pair <llint, llint> pi;
typedef vector <int> Vi;
typedef vector <llint> vi;

const int MAXN = 91;
const int MAXM = 91 * 91; 
const llint INF = 1000000000000000000LL;

llint n, m, s, q, br;
llint len[MAXM], c[MAXM];
llint path[MAXN][MAXN], bio[MAXN][MAXN];
vector <pi> v[MAXN];

int p[MAXN][MAXN];
int best[MAXN], siz[MAXN];
llint dist[MAXN][MAXN][MAXN * MAXN], best_val[MAXN];
vi times[MAXN];

void dijkstra (int root) {
	for (int i = 0; i < n; i++) {
		path[root][i] = INF;
	}
	path[root][root] = 0;
	for (int i = 0; i < n; i++) {
		llint mn = INF, ind = -1;
		for (int j = 0; j < n; j++) {
			if (bio[root][j] == 0 && path[root][j] < mn) {
				mn = path[root][j];
				ind = j;
			}
		}
		bio[root][ind] = 1;
		for (auto pp : v[ind]) {
			int sus = pp.first, e = pp.second;
			llint novi = path[root][ind] + len[e];
			if (path[root][ind] % s <= c[e] - len[e]) {
				path[root][sus] = min(path[root][sus], novi);
			}
			novi += s - path[root][ind] % s;
			path[root][sus] = min(path[root][sus], novi);
		}
	}
}

void init () {
	for (int i = 0; i < n; i++) {
		times[i].push_back(-(s - 1));
		siz[i] = 1;
		for (int j = 0; j < n; j++) {
			dist[i][j][0] = INF;
			p[i][j] = (int)v[j].size() - 1;
		}
		dist[i][i][0] = s - 1;
		best[i] = i;
		int e = v[i].back().second;
		best_val[i] = c[e] - len[e];
	}
}

int get_best_root () {
	llint mx = -INF, ind = -1;
	for (int i = 0; i < n; i++) {
		if (best_val[i] > mx) {
			mx = best_val[i];
			ind = i;
		}
	}
	return ind;
}

void upd_dist (int root, int node, llint d) {
	//if (br <= 100) cout << "upd_dist " << root << " " << node << " " << d << endl;
	int ind = upper_bound(times[node].begin(), times[node].end(), -d) - times[node].begin() - 1;
	llint curr_x = -times[node][ind];
	for (int i = 0; i < n; i++) {
		if (dist[node][i][ind] == INF) continue;
		llint val = dist[node][i][ind] - curr_x + d;
		dist[root][i][siz[root]] = min(dist[root][i][siz[root]], val);
	}
}

bool upd_best (int root) {
	llint mx = -INF, ind = -1;
	bool smanjio = 0;
	for (int i = 0; i < n; i++) {
		while (p[root][i] >= 0) {
			llint val = dist[root][i][siz[root]];
			if (val == INF) break;
		
			int sus = v[i][p[root][i]].first;
			int e = v[i][p[root][i]].second;
			if (val > c[e] - len[e]) {
				llint tmp = dist[root][root][siz[root]] - (val - (c[e] - len[e]));
				if (tmp > mx) {
					mx = tmp;
					ind = i;
				}
				break;
			}
			upd_dist(root, sus, val + len[e]);
			p[root][i]--;
			smanjio = 1;
		}
	}
	best[root] = ind;
	best_val[root] = mx;
	return smanjio;
}

void ispis (int root, int ind) {
	cout << "ispis " << root << endl;
	for (int i = 0; i < n; i++) {
		cout << "bla " << i << " " << dist[root][i][ind] << endl;
	}
	cout << endl;
}

void calc () {
	while (1) {
		br++;
		int root = get_best_root();
		if (root == -1) break;
		int node = best[root];
		//if (br <= 5) cout << "sad na " << root << " " << node << endl;
		
		int sus = v[node][p[root][node]].first;
		int e = v[node][p[root][node]].second;
		llint del = dist[root][node][siz[root] - 1] - (c[e] - len[e]);
		
		for (int i = 0; i < n; i++) {
			if (dist[root][i][siz[root] - 1] != INF) {
				dist[root][i][siz[root]] = dist[root][i][siz[root] - 1] - del;
			} else {
				dist[root][i][siz[root]] = INF;
			}
		}
		while (upd_best(root));
		times[root].push_back(-dist[root][root][siz[root]]);
		siz[root]++;
		
		//if (br <= 5) ispis(root, siz[root] - 1);
	}
	/*for (int i = 0; i < n; i++) {
		cout << "bla " << i << "  ";
		for (auto t : times[i]) cout << t << " "; cout << endl;
	}*/
	//ispis(0, 2);
}

bool cmp (pi a, pi b) {
	int ia = a.second, ib = b.second;
	return c[ia] - len[ia] < c[ib] - len[ib];
}

llint upit (int root, int node, llint d) {
	int ind = upper_bound(times[root].begin(), times[root].end(), -d) - times[root].begin() - 1;
	llint curr_x = -times[root][ind];
	if (dist[root][node][ind] != INF) {
		return dist[root][node][ind] - curr_x;
	} else {
		llint res = INF;
		for (int i = 0; i < n; i++) {
			if (dist[root][i][ind] != INF) {
				res = min(res, s + path[i][node]);
			}
		}
		return res - d;
	}
}

vi calculate_necessary_time (int N, int M, llint S, int Q, 
							 Vi A, Vi B, vi L, vi C, Vi U, Vi V, vi T) {
	n = N; m = M; s = S; q = Q;
	for (int i = 0; i < m; i++) {
		len[i] = L[i];
		c[i] = C[i];
		v[A[i]].push_back({B[i], i});
		v[B[i]].push_back({A[i], i});
	}
	for (int i = 0; i < n; i++) {
		sort(v[i].begin(), v[i].end(), cmp);
	}
	init();
	calc();
	for (int i = 0; i < n; i++) dijkstra(i);
	vi sol;
	for (int i = 0; i < q; i++) {
		sol.push_back(upit(U[i], V[i], T[i]));
	}
	return sol;
}

Compilation message

escape_route.cpp: In function 'void calc()':
escape_route.cpp:132:7: warning: unused variable 'sus' [-Wunused-variable]
  132 |   int sus = v[node][p[root][node]].first;
      |       ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65076 KB Output is correct
2 Correct 59 ms 65004 KB Output is correct
3 Correct 133 ms 65012 KB Output is correct
4 Correct 32 ms 64964 KB Output is correct
5 Correct 55 ms 65000 KB Output is correct
6 Correct 39 ms 64972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 130952 KB Output is correct
2 Correct 602 ms 197960 KB Output is correct
3 Correct 748 ms 178432 KB Output is correct
4 Correct 779 ms 207748 KB Output is correct
5 Correct 769 ms 207448 KB Output is correct
6 Correct 32 ms 64964 KB Output is correct
7 Correct 697 ms 178184 KB Output is correct
8 Correct 665 ms 202760 KB Output is correct
9 Correct 642 ms 167536 KB Output is correct
10 Correct 777 ms 207136 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65076 KB Output is correct
2 Correct 59 ms 65004 KB Output is correct
3 Correct 133 ms 65012 KB Output is correct
4 Correct 32 ms 64964 KB Output is correct
5 Correct 55 ms 65000 KB Output is correct
6 Correct 39 ms 64972 KB Output is correct
7 Correct 628 ms 130952 KB Output is correct
8 Correct 602 ms 197960 KB Output is correct
9 Correct 748 ms 178432 KB Output is correct
10 Correct 779 ms 207748 KB Output is correct
11 Correct 769 ms 207448 KB Output is correct
12 Correct 32 ms 64964 KB Output is correct
13 Correct 697 ms 178184 KB Output is correct
14 Correct 665 ms 202760 KB Output is correct
15 Correct 642 ms 167536 KB Output is correct
16 Correct 777 ms 207136 KB Output is correct
17 Correct 930 ms 178136 KB Output is correct
18 Correct 900 ms 175380 KB Output is correct
19 Correct 829 ms 200920 KB Output is correct
20 Correct 1247 ms 180452 KB Output is correct
21 Correct 1146 ms 210224 KB Output is correct
22 Correct 1127 ms 210064 KB Output is correct
23 Correct 1091 ms 179732 KB Output is correct
24 Correct 1453 ms 202612 KB Output is correct
25 Correct 1008 ms 168084 KB Output is correct
26 Correct 1235 ms 207188 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65076 KB Output is correct
2 Correct 59 ms 65004 KB Output is correct
3 Correct 133 ms 65012 KB Output is correct
4 Correct 32 ms 64964 KB Output is correct
5 Correct 55 ms 65000 KB Output is correct
6 Correct 39 ms 64972 KB Output is correct
7 Correct 628 ms 130952 KB Output is correct
8 Correct 602 ms 197960 KB Output is correct
9 Correct 748 ms 178432 KB Output is correct
10 Correct 779 ms 207748 KB Output is correct
11 Correct 769 ms 207448 KB Output is correct
12 Correct 32 ms 64964 KB Output is correct
13 Correct 697 ms 178184 KB Output is correct
14 Correct 665 ms 202760 KB Output is correct
15 Correct 642 ms 167536 KB Output is correct
16 Correct 777 ms 207136 KB Output is correct
17 Correct 930 ms 178136 KB Output is correct
18 Correct 900 ms 175380 KB Output is correct
19 Correct 829 ms 200920 KB Output is correct
20 Correct 1247 ms 180452 KB Output is correct
21 Correct 1146 ms 210224 KB Output is correct
22 Correct 1127 ms 210064 KB Output is correct
23 Correct 1091 ms 179732 KB Output is correct
24 Correct 1453 ms 202612 KB Output is correct
25 Correct 1008 ms 168084 KB Output is correct
26 Correct 1235 ms 207188 KB Output is correct
27 Correct 1695 ms 263160 KB Output is correct
28 Correct 1538 ms 249120 KB Output is correct
29 Correct 1392 ms 281744 KB Output is correct
30 Correct 2293 ms 262308 KB Output is correct
31 Correct 1897 ms 291344 KB Output is correct
32 Correct 1853 ms 292012 KB Output is correct
33 Correct 2776 ms 215420 KB Output is correct
34 Correct 1657 ms 253368 KB Output is correct
35 Correct 1859 ms 292156 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65076 KB Output is correct
2 Correct 59 ms 65004 KB Output is correct
3 Correct 133 ms 65012 KB Output is correct
4 Correct 32 ms 64964 KB Output is correct
5 Correct 55 ms 65000 KB Output is correct
6 Correct 39 ms 64972 KB Output is correct
7 Correct 628 ms 130952 KB Output is correct
8 Correct 602 ms 197960 KB Output is correct
9 Correct 748 ms 178432 KB Output is correct
10 Correct 779 ms 207748 KB Output is correct
11 Correct 769 ms 207448 KB Output is correct
12 Correct 32 ms 64964 KB Output is correct
13 Correct 697 ms 178184 KB Output is correct
14 Correct 665 ms 202760 KB Output is correct
15 Correct 642 ms 167536 KB Output is correct
16 Correct 777 ms 207136 KB Output is correct
17 Correct 930 ms 178136 KB Output is correct
18 Correct 900 ms 175380 KB Output is correct
19 Correct 829 ms 200920 KB Output is correct
20 Correct 1247 ms 180452 KB Output is correct
21 Correct 1146 ms 210224 KB Output is correct
22 Correct 1127 ms 210064 KB Output is correct
23 Correct 1091 ms 179732 KB Output is correct
24 Correct 1453 ms 202612 KB Output is correct
25 Correct 1008 ms 168084 KB Output is correct
26 Correct 1235 ms 207188 KB Output is correct
27 Correct 1695 ms 263160 KB Output is correct
28 Correct 1538 ms 249120 KB Output is correct
29 Correct 1392 ms 281744 KB Output is correct
30 Correct 2293 ms 262308 KB Output is correct
31 Correct 1897 ms 291344 KB Output is correct
32 Correct 1853 ms 292012 KB Output is correct
33 Correct 2776 ms 215420 KB Output is correct
34 Correct 1657 ms 253368 KB Output is correct
35 Correct 1859 ms 292156 KB Output is correct
36 Correct 4700 ms 673000 KB Output is correct
37 Correct 3877 ms 591116 KB Output is correct
38 Correct 6382 ms 661280 KB Output is correct
39 Correct 4838 ms 697948 KB Output is correct
40 Correct 4767 ms 698844 KB Output is correct
41 Correct 4558 ms 244032 KB Output is correct
42 Correct 4482 ms 670264 KB Output is correct
43 Correct 3888 ms 585232 KB Output is correct