Submission #1171544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171544		OI_Account	Escape Route (JOI21_escape_route)	C++20	5 / 100	9086 ms	120716 KiB

escape_route

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

typedef long long ll;
typedef vector<int> vii;
typedef vector<ll> vll;

const int N = 90;
const int M = N * N / 2;
const int S = 4000;
const int Q = 3'000'000;
const ll INF = 1'000'000'000'000'000'000;

int n, m, q;
ll l[M + 10], c[M + 10], s;
ll x[Q + 10], y[Q + 10], t[Q + 10], ans[Q + 10];
ll dis0[N + 10][N + 10], mxT[N + 10][N + 10];
ll dis[N + 10][S + 10][N + 10];
ll d[N + 10], tim[N + 10];
vector<ll> imp[N + 10];
vector<pair<int, int>> adj[N + 10];

void calcDisType1(int r, ll timSt) {
    for (int i = 1; i <= n; i++)
        d[i] = INF;
    set<pair<ll, int>> st;
    st.insert({0, r});
    d[r] = 0;
    tim[r] = timSt;
    while (!st.empty()) {
        int u = st.begin() -> second;
        st.erase(st.begin());
        for (auto [v, e]: adj[u]) {
            ll newDis = d[v], newTim;
            if (tim[u] <= c[e]) {
                if (d[u] + l[e] < d[v]) {
                    newDis = d[u] + l[e];
                    newTim = tim[u] + l[e];
                }
            }
            else if (d[u] + s - tim[u] + l[e] < d[v]) {
                newDis = d[u] + s - tim[u] + l[e];
                newTim = l[e];
            }
            if (newDis < d[v]) {
                st.erase({d[v], v});
                d[v] = newDis;
                tim[v] = newTim;
                st.insert({d[v], v});
            }
        }
    }
}

void calcDis0() {
    for (int i = 1; i <= n; i++) {
        calcDisType1(i, 0);
        for (int j = 1; j <= n; j++)
            dis0[i][j] = d[j];
    }
}

void solve() {
    for (int i = 1; i <= q; i++) {
        calcDisType1(x[i], t[i]);
        ans[i] = d[y[i]];
    }
}

vll writeOutput() {
    vll res;
    for (int i = 1; i <= q; i++)
        res.push_back(ans[i]);
    return res;
}

vll calculate_necessary_time(int N, int M, ll S, int Q, vii A, vii B, vll L, vll C, vii U, vii V, vll T) {
    n = N;
    m = M;
    s = S;
    q = Q;
    for (int i = 0; i < m; i++) {
        int u = A[i] + 1, v = B[i] + 1;
        adj[u].push_back({v, i + 1});
        adj[v].push_back({u, i + 1});
        l[i + 1] = L[i];
        c[i + 1] = C[i] - L[i];
    }
    for (int i = 0; i < q; i++) {
        x[i + 1] = U[i] + 1;
        y[i + 1] = V[i] + 1;
        t[i + 1] = T[i];
    }
    solve();
    return writeOutput();
}

/*int main() {
    int n, m;
    ll s;
    int q;
    vii A, B, U, V;
    vll L, C, T;
    cin >> n >> m >> s >> q;
    for (int i = 1; i <= m; i++) {
        int x, y;
        ll z, t;
        cin >> x >> y >> z >> t;
        A.push_back(x);
        B.push_back(y);
        L.push_back(z);
        C.push_back(t);
    }
    int Q = q;
    U.resize(Q);
    V.resize(Q);
    T.resize(Q);
    for (int i = 0; i < q; i++)
        cin >> U[i] >> V[i] >> T[i];
    vll ans = calculate_necessary_time(n, m, s, q, A, B, L, C, U, V, T);
    for (auto x: ans)
        cout << x << ' ';
    cout << endl;
    return 0;
}*/

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