Submission #393873

#	Time	Username	Problem	Language	Result	Execution time	Memory
393873		keko37	Escape Route (JOI21_escape_route)	C++17	100 / 100	6382 ms	698844 KiB

escape_route

#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 (stderr)

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 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 30 / 30