oj.uz

Submission #393039

# Submission time Handle Problem Language Result Execution time Memory
393039 2021-04-22T15:26:29 Z Mlxa Escape Route (JOI21_escape_route) C++17
0 / 100
 9000 ms 154968 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 64920 KB Output is correct
2 Incorrect 47 ms 65044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9048 ms 154968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 64920 KB Output is correct
2 Incorrect 47 ms 65044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 64920 KB Output is correct
2 Incorrect 47 ms 65044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 64920 KB Output is correct
2 Incorrect 47 ms 65044 KB Output isn't correct
3 Halted 0 ms 0 KB -