Submission #709744

#	Time	Username	Problem	Language	Result	Execution time	Memory
709744		PixelCat	Escape Route (JOI21_escape_route)	C++17	5 / 100	9060 ms	136104 KiB

escape_route

#include "escape_route.h"

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define MOD (int)(1000000007)
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100;
const int INF = 8e18;

struct Edge {
    int c, l;  // close time, length
};

int N, M, S, Q;
Edge adj[MAXN][MAXN];
pii owo[MAXN][MAXN];
int vis[MAXN];
int dist[MAXN];

// starting from time=0
void meow(int s) {
    For(i, 0, N - 1) {
        owo[s][i] = pii(INF, INF);
        vis[i] = 0;
    }
    using Route = pair<pii, int>; // {{day, time}, index}
    priority_queue<Route, vector<Route>, greater<Route>> pq;
    pq.emplace(pii(0, 0), s);
    owo[s][s] = pii(0, 0);
    while(!pq.empty()) {
        int d, t, cur;
        tie(d, t) = pq.top().first;
        cur = pq.top().second;
        pq.pop();
        if(vis[cur]) continue;
        vis[cur] = 1;
        For(i, 0, N - 1) if(adj[cur][i].l > 0) {
            auto &e = adj[cur][i];
            pii nt;
            if(t + e.l <= e.c) nt = pii(d, t + e.l);
            else nt = pii(d + 1, e.l);
            if(nt < owo[s][i]) {
                owo[s][i] = nt;
                pq.emplace(nt, i);
            }
        }
    }
}

int nya(int u, int v, int t) {
    For(i, 0, N - 1) {
        dist[i] = INF;
        vis[i] = 0;
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.emplace(t, u);
    dist[u] = t;
    while(!pq.empty()) {
        int d, cur;
        tie(d, cur) = pq.top();
        pq.pop();
        if(vis[cur]) continue;
        vis[cur] = 1;
        For(i, 0, N - 1) if(adj[cur][i].l > 0) {
            auto &e = adj[cur][i];
            int nd = d + e.l;
            if(nd <= e.c && nd < dist[i]) {
                dist[i] = nd;
                pq.emplace(nd, i);
            }
        }
    }
    if(dist[v] != INF) return dist[v] - dist[u];
    int ans = INF;
    For(i, 0, N - 1) if(dist[i] != INF) {
        auto tm = owo[i][v];
        ans = min(ans, S * (tm.first + 1) + tm.second - dist[u]);
    }
    // cout << ans << "\n";
    // For(i, 0, N - 1) cout << dist[i] << " \n"[i == N - 1];
    // cout << flush;
    return ans;
}

std::vector<long long> calculate_necessary_time(
    int32_t _N, int32_t _M, long long _S, int32_t _Q, std::vector<int32_t> A, std::vector<int32_t> B,
    std::vector<long long> L, std::vector<long long> C, std::vector<int32_t> U,
    std::vector<int32_t> V, std::vector<long long> T) {
    N = _N; M = _M; S = _S; Q = _Q;
    For(i, 0, N - 1) For(j, 0, N - 1) {
        adj[i][j] = {-1, -1};
    }
    For(i, 0, M - 1) {
        int a = A[i];
        int b = B[i];
        int l = L[i];
        int c = C[i];
        adj[a][b] = adj[b][a] = {c, l};
    }
    For(i, 0, N - 1) meow(i);
    vector<int> res;
    For(i, 0, Q - 1) {
        res.eb(nya(U[i], V[i], T[i]));
    }
    // cout << res.back() << "\n";
    // For(i, 0, N - 1) For(j, 0, N - 1) {
    //     cout << owo[i][j].first << "+" << owo[i][j].second << " \n"[j == N - 1];
    // }
    return res;
}

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