oj.uz

Submission #521951

# Submission time Handle Problem Language Result Execution time Memory
521951 2022-02-03T13:47:30 Z eecs Escape Route (JOI21_escape_route) C++17
70 / 100
 1459 ms 246408 KB 
// not my code
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Prique {
    const ll INF = 4 * (ll)1e18;
    vector<pair<ll, int>> data;
    const int n;

    Prique(int siz) : n(siz), data(2 * siz, {INF, -1}) { data[0] = {-INF, -1}; }
    void push(int i, ll v) {
        data[i + n] = {v, (v >= INF ? -1 : i)};
        for (i += n; i > 1; i >>= 1)
            data[i >> 1] = min(data[i], data[i ^ 1]);
    }
    void decKey(int i, ll v) {
        for (int j = i + n; data[j].first > v; j >>= 1)
            data[j] = {v, i};
    }
    pair<ll, int> pop() {
        auto res = data[1];
        push(res.second, INF);
        return res;
    }
};

const int N = 65;
const ll INF = 1e18;
ll tight_times[N][N][N];
ll wts[N][N], cs[N][N];
vector<pair<ll, int>> qs[N], ord[N];

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) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            wts[i][j] = 0;
            cs[i][j] = -1;
        }
        cs[i][i] = 0;
    }
    for (int i = 0; i < n; ++i) {
        qs[i].clear();
        qs[i].shrink_to_fit();
        ord[i].clear();
        ord[i].shrink_to_fit();
    }

    for (int j = 0; j < m; ++j) {
        int a = A[j];
        int b = B[j];
        wts[a][b] = L[j];
        wts[b][a] = L[j];
        cs[a][b] = C[j] - L[j];
        cs[b][a] = C[j] - L[j];
    }

    for (int i = 0; i < n; ++i) {
        for (int x = 0; x < n; ++x) {
            for (int j = 0; j < n; ++j)
                tight_times[i][x][j] = INF;
            if (cs[i][x] == -1)
                continue;

            tight_times[i][x][i] = cs[i][x];

            Prique que(n);
            for (int j = i; j != -1; j = que.pop().second) {
                ll base = tight_times[i][x][j];
                ll sec = base % s;
                ll nxt = base + (s - sec);
                for (int t = 0; t < n; ++t) {
                    ll c = cs[j][t];
                    if (c == -1)
                        continue;

                    ll off = (c < sec ? nxt : base) + wts[j][t];
                    if (off < tight_times[i][x][t]) {
                        tight_times[i][x][t] = off;
                        que.decKey(t, off);
                    }
                }
            }
        }
    }

    for (int j = 0; j < q; ++j) {
        qs[U[j]].emplace_back(T[j], j);
    }

    for (int i = 0; i < n; ++i) {
        sort(qs[i].begin(), qs[i].end());
        reverse(qs[i].begin(), qs[i].end());

        ord[i].resize(n);
        for (int j = 0; j < n; ++j)
            ord[i][j] = make_pair(cs[i][j], j);

        sort(ord[i].begin(), ord[i].end());
        reverse(ord[i].begin(), ord[i].end());
    }

    vector<ll> ans(q, INF);
    for (int i = 0; i < n; ++i) {
        vector<int> inds(n, 0);
        vector<ll> cur_dist(n, INF);
        cur_dist[i] = 0;

        int qi = 0;

        Prique que(n);
        que.decKey(i, -ord[i][inds[i]].first);
        while (true) {
            auto pr = que.pop();
            ll next_time = -pr.first;

            // Answer queries
            while (qi < qs[i].size() && qs[i][qi].first > next_time) {
                int ind = qs[i][qi].second;

                // Answer if possible in one day
                ans[ind] = min(ans[ind], cur_dist[V[ind]]);

                // Answer if need multiple days
                for (int t = 0; t < n; ++t) {
                    if (cur_dist[t] <= s)
                        ans[ind] = min(ans[ind],
                                       s - T[ind] + tight_times[t][t][V[ind]]);
                }

                ++qi;
            }

            if (next_time < 0)
                break;

            // Update distances
            int j = pr.second;
            int x = ord[j][inds[j]].second;
            ++inds[j];

            if (inds[j] < n)
                que.decKey(j, -(ord[j][inds[j]].first - cur_dist[j]));

            for (int t = 0; t < n; ++t) {
                if (tight_times[j][x][t] >= s)
                    continue;

                ll off = cur_dist[j] + tight_times[j][x][t] - cs[j][x];
                if (off < cur_dist[t]) {
                    cur_dist[t] = off;
                    if (inds[t] < n) {
                        que.decKey(
                            t, -min(next_time, ord[t][inds[t]].first - off));
                    }
                }
            }
        }
    }
    return ans;
}

Compilation message

escape_route.cpp: In constructor 'Prique::Prique(int)':
escape_route.cpp:9:15: warning: 'Prique::n' will be initialized after [-Wreorder]
    9 |     const int n;
      |               ^
escape_route.cpp:8:27: warning:   'std::vector<std::pair<long long int, int> > Prique::data' [-Wreorder]
    8 |     vector<pair<ll, int>> data;
      |                           ^~~~
escape_route.cpp:11:5: warning:   when initialized here [-Wreorder]
   11 |     Prique(int siz) : n(siz), data(2 * siz, {INF, -1}) { data[0] = {-INF, -1}; }
      |     ^~~~~~
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:121:23: 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]
  121 |             while (qi < qs[i].size() && qs[i][qi].first > next_time) {
      |                    ~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64972 KB Output is correct
2 Correct 31 ms 65032 KB Output is correct
3 Correct 57 ms 65092 KB Output is correct
4 Correct 25 ms 64944 KB Output is correct
5 Correct 30 ms 64988 KB Output is correct
6 Correct 25 ms 65060 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1169 ms 196976 KB Output is correct
2 Correct 1190 ms 220212 KB Output is correct
3 Correct 1153 ms 201448 KB Output is correct
4 Correct 1214 ms 229740 KB Output is correct
5 Correct 1300 ms 229840 KB Output is correct
6 Correct 30 ms 64964 KB Output is correct
7 Correct 1156 ms 200840 KB Output is correct
8 Correct 1184 ms 242320 KB Output is correct
9 Correct 1162 ms 189096 KB Output is correct
10 Correct 1272 ms 229312 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64972 KB Output is correct
2 Correct 31 ms 65032 KB Output is correct
3 Correct 57 ms 65092 KB Output is correct
4 Correct 25 ms 64944 KB Output is correct
5 Correct 30 ms 64988 KB Output is correct
6 Correct 25 ms 65060 KB Output is correct
7 Correct 1169 ms 196976 KB Output is correct
8 Correct 1190 ms 220212 KB Output is correct
9 Correct 1153 ms 201448 KB Output is correct
10 Correct 1214 ms 229740 KB Output is correct
11 Correct 1300 ms 229840 KB Output is correct
12 Correct 30 ms 64964 KB Output is correct
13 Correct 1156 ms 200840 KB Output is correct
14 Correct 1184 ms 242320 KB Output is correct
15 Correct 1162 ms 189096 KB Output is correct
16 Correct 1272 ms 229312 KB Output is correct
17 Correct 1177 ms 200376 KB Output is correct
18 Correct 1133 ms 199084 KB Output is correct
19 Correct 1230 ms 225476 KB Output is correct
20 Correct 1200 ms 203508 KB Output is correct
21 Correct 1222 ms 232292 KB Output is correct
22 Correct 1269 ms 232912 KB Output is correct
23 Correct 1137 ms 202752 KB Output is correct
24 Correct 1220 ms 246408 KB Output is correct
25 Correct 1129 ms 192448 KB Output is correct
26 Correct 1227 ms 231716 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64972 KB Output is correct
2 Correct 31 ms 65032 KB Output is correct
3 Correct 57 ms 65092 KB Output is correct
4 Correct 25 ms 64944 KB Output is correct
5 Correct 30 ms 64988 KB Output is correct
6 Correct 25 ms 65060 KB Output is correct
7 Correct 1169 ms 196976 KB Output is correct
8 Correct 1190 ms 220212 KB Output is correct
9 Correct 1153 ms 201448 KB Output is correct
10 Correct 1214 ms 229740 KB Output is correct
11 Correct 1300 ms 229840 KB Output is correct
12 Correct 30 ms 64964 KB Output is correct
13 Correct 1156 ms 200840 KB Output is correct
14 Correct 1184 ms 242320 KB Output is correct
15 Correct 1162 ms 189096 KB Output is correct
16 Correct 1272 ms 229312 KB Output is correct
17 Correct 1177 ms 200376 KB Output is correct
18 Correct 1133 ms 199084 KB Output is correct
19 Correct 1230 ms 225476 KB Output is correct
20 Correct 1200 ms 203508 KB Output is correct
21 Correct 1222 ms 232292 KB Output is correct
22 Correct 1269 ms 232912 KB Output is correct
23 Correct 1137 ms 202752 KB Output is correct
24 Correct 1220 ms 246408 KB Output is correct
25 Correct 1129 ms 192448 KB Output is correct
26 Correct 1227 ms 231716 KB Output is correct
27 Correct 1270 ms 201636 KB Output is correct
28 Correct 1436 ms 201084 KB Output is correct
29 Correct 1459 ms 222196 KB Output is correct
30 Correct 1304 ms 203324 KB Output is correct
31 Correct 1387 ms 230656 KB Output is correct
32 Correct 1359 ms 231280 KB Output is correct
33 Correct 1305 ms 242136 KB Output is correct
34 Correct 1265 ms 192420 KB Output is correct
35 Correct 1361 ms 230744 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64972 KB Output is correct
2 Correct 31 ms 65032 KB Output is correct
3 Correct 57 ms 65092 KB Output is correct
4 Correct 25 ms 64944 KB Output is correct
5 Correct 30 ms 64988 KB Output is correct
6 Correct 25 ms 65060 KB Output is correct
7 Correct 1169 ms 196976 KB Output is correct
8 Correct 1190 ms 220212 KB Output is correct
9 Correct 1153 ms 201448 KB Output is correct
10 Correct 1214 ms 229740 KB Output is correct
11 Correct 1300 ms 229840 KB Output is correct
12 Correct 30 ms 64964 KB Output is correct
13 Correct 1156 ms 200840 KB Output is correct
14 Correct 1184 ms 242320 KB Output is correct
15 Correct 1162 ms 189096 KB Output is correct
16 Correct 1272 ms 229312 KB Output is correct
17 Correct 1177 ms 200376 KB Output is correct
18 Correct 1133 ms 199084 KB Output is correct
19 Correct 1230 ms 225476 KB Output is correct
20 Correct 1200 ms 203508 KB Output is correct
21 Correct 1222 ms 232292 KB Output is correct
22 Correct 1269 ms 232912 KB Output is correct
23 Correct 1137 ms 202752 KB Output is correct
24 Correct 1220 ms 246408 KB Output is correct
25 Correct 1129 ms 192448 KB Output is correct
26 Correct 1227 ms 231716 KB Output is correct
27 Correct 1270 ms 201636 KB Output is correct
28 Correct 1436 ms 201084 KB Output is correct
29 Correct 1459 ms 222196 KB Output is correct
30 Correct 1304 ms 203324 KB Output is correct
31 Correct 1387 ms 230656 KB Output is correct
32 Correct 1359 ms 231280 KB Output is correct
33 Correct 1305 ms 242136 KB Output is correct
34 Correct 1265 ms 192420 KB Output is correct
35 Correct 1361 ms 230744 KB Output is correct
36 Runtime error 271 ms 157376 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -