Submission #521992

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
521992	2022-02-03 14:51:33	eecs	Escape Route (JOI21_escape_route)	C++17	100 / 100	4536 ms	144592 KiB

escape_route

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
void chk(ll &x, ll y) {
    if (x > y) x = y;
}
vector<ll> calculate_necessary_time(int n, 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) {
    vector<vector<ll>> W(n, vector<ll>(n, -1)), lim = W;
    for (int i = 0; i < m; i++) {
        W[A[i]][B[i]] = W[B[i]][A[i]] = L[i];
        lim[A[i]][B[i]] = lim[B[i]][A[i]] = C[i] - L[i];
    }
    auto dijkstra = [&](vector<ll> &d) {
        vector<bool> vis(n);
        while (1) {
            int u = -1;
            for (int i = 0; i < n; i++) {
                if (!vis[i] && d[i] < INF && (!~u || d[u] > d[i])) u = i;
            }
            if (!~u) break;
            vis[u] = 1;
            for (int i = 0; i < n; i++) if (~W[u][i]) {
                if (d[u] % S <= lim[u][i]) chk(d[i], d[u] + W[u][i]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, ll, 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:72:29: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             tim[u] = cur[u] < G[u].size() ? lim[u][G[u][cur[u]]] - dist[u] : -1;
escape_route.cpp:75:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 if (cur[i] < G[i].size()) tim[i] = lim[i][G[i][cur[i]]] - dist[i];

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