Submission #393039

#	Time	Username	Problem	Language	Result	Execution time	Memory
393039		Mlxa	Escape Route (JOI21_escape_route)	C++17	0 / 100	9048 ms	154968 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

namespace my {
const int N   = 92;
const ll INF = 1e18;

struct edge {
	ll u;
	ll w;
	ll h;
	edge(ll x, ll y, ll z) : u(x), w(y), h(z) {}
	operator int() {
		return u;
	}
};

int n;
ll s;
vector<edge> g[N];
ll dist[N];
bool used[N];

ll near(int h) {
	return (h + s - 1) / s * s;
}

ll query(ll v, ll to, ll t) {
	fill_n(dist, N, INF);
	fill_n(used, N, false);
	dist[v] = t;
	for (int it = 0; it < n; ++it) {
		v = -1;
		for (int i = 0; i < n; ++i) {
			if (used[i]) {
				continue;
			}
			if (v == -1 || dist[v] > dist[i]) {
				v = i;
			}
		}
		used[v] = true;
		for (edge u : g[v]) {
			ll can = dist[v] + u.w;
			if (can % s > u.h || (can / s) > (dist[v] / s)) {
				can = near(dist[v]) + u.w;
			}
			// cout << v << " " << u << " " << dist[v] << " " << can << endl;
			if (dist[u] > can) {
				dist[u] = can;
			}
		}
	}
	return dist[to] - t;
}
}

vector<ll> calculate_necessary_time(
	int nn, int M, ll S, int Q, vector<int> A, vector<int> B,
	vector<ll> L, vector<ll> C, vector<int> U,
	vector<int> V, vector<ll> T) {
	using namespace my;
	n = nn, s = S;
	for (int i = 0; i < M; ++i) {
		g[A[i]].emplace_back(B[i], L[i], C[i]);
		g[B[i]].emplace_back(A[i], L[i], C[i]);
	}
	vector<ll> ans(Q);
	for (int i = 0; i < Q; ++i) {
		ans[i] = query(U[i], V[i], T[i]);
	}

	return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30