Submission #634035

#	Time	Username	Problem	Language	Result	Execution time	Memory
634035		valerikk	Escape Route (JOI21_escape_route)	C++17	100 / 100	2959 ms	193780 KiB

escape_route

#include "escape_route.h"
#include <algorithm>
#include <iostream>
 
using std::vector;
using std::pair;
 
using ll = long long;
 
const ll INF = 1e18;
 
vector<ll> dijkstra(int N, ll S, int st, ll T, vector<vector<ll>> &l, vector<vector<ll>> &c) {
	vector<ll> t(N, INF);
	vector<bool> used(N, 0);
	t[st] = T;
	for (int it = 0; it < N; ++it) {
		int u = -1;
		for (int i = 0; i < N; ++i) {
			if (!used[i] && (u == -1 || t[i] < t[u]))
				u = i;
		}
		if (t[u] == INF) break;
		used[u] = 1;
		for (int v = 0; v < N; ++v) {
			if (!used[v] && l[u][v] < S) {
				ll t1 = t[u] + l[u][v];
				if (t[u] % S + l[u][v] > c[u][v]) 
					t1 += S - t[u] % S;
				t[v] = std::min(t[v], t1);
			}
		}
	}
	return t;
}
 
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) {
	
	vector<vector<ll>> l(N, vector<ll>(N, S));
	vector<vector<ll>> c(N, vector<ll>(N, S));
	for (int i = 0; i < M; ++i) {
		l[A[i]][B[i]] = l[B[i]][A[i]] = L[i];
		c[A[i]][B[i]] = c[B[i]][A[i]] = C[i];
	}
	for (int i = 0; i < N; ++i) {
		l[i][i] = 0;
		c[i][i] = 0;
	}
	vector<vector<vector<ll>>> t(N, vector<vector<ll>>(N));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (l[i][j] < S) 
				t[i][j] = dijkstra(N, S, j, c[i][j], l, c);
		}
	}
	vector<ll> ans(Q);
	for (int i = 0; i < Q; ++i) {
		ans[i] = t[U[i]][U[i]][V[i]] + (S - T[i]) % S;
	}
	for (int st = 0; st < N; ++st) {
		vector<pair<ll, int>> que;
		for (int i = 0; i < Q; ++i) {
			if (U[i] == st) 
				que.push_back({T[i], i});
		}
		std::sort(que.rbegin(), que.rend());
		vector<vector<pair<ll, int>>> ord(N);
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (i != j && l[i][j] < S) 
					ord[i].push_back({c[i][j] - l[i][j], j});
			}
			std::sort(ord[i].rbegin(), ord[i].rend());
		}
		vector<int> ind(N, 0);
		vector<ll> d(N, INF);
		d[st] = 0;
		int ptr = 0;
		while (1) {		
			pair<ll, int> max = {-1, -1};
			for (int i = 0; i < N; ++i) {
				if (ind[i] < ord[i].size()) 
					max = std::max(max, {ord[i][ind[i]].first - d[i], i});
			}
			while (ptr < que.size() && que[ptr].first > max.first) {
				int id = que[ptr++].second;
				// std::cerr << id << " " << d[V[id]] << "\n";
				ans[id] = std::min(ans[id], d[V[id]]);
				for (int i = 0; i < N; ++i) {
					if (d[i] < INF) 
						ans[id] = std::min(ans[id], S - T[id] + t[i][i][V[id]]);
				}
			}
			if (max.first < 0) break;
			int u = max.second;
			int v = ord[u][ind[u]++].second;
			for (int i = 0; i < N; ++i) {
				if (t[u][v][i] < S) 
					d[i] = std::min(d[i], t[u][v][i] - max.first);
			}
		}
	}
	return ans;
}

Compilation message (stderr)

escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, long long int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::vector<long long int>)':
escape_route.cpp:84:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     if (ind[i] < ord[i].size())
escape_route.cpp:87:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    while (ptr < que.size() && que[ptr].first > max.first) {
      |           ~~~~^~~~~~~~~~~~

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